  In this paper, we give a number of new exact algorithms and heuristics to
compute linear boolean decompositions, and experimentally evaluate these
algorithms. The experimental evaluation shows that significant improvements can
be made with respect to running time without increasing the width of the
generated decompositions. We also evaluated dynamic programming algorithms on
linear boolean decompositions for several vertex subset problems. This
evaluation shows that such algorithms are often much faster (up to several
orders of magnitude) compared to theoretical worst case bounds.
