Variations on Boolean-width
Summary
This thesis is about the graph parameter boolean-width and several related
parameters. In particular we investigate the restriction of boolean-width to
linear decompositions, called linear boolean-width. Improving upon existing
work, we give several new algorithms, both exact and heuristical, and test
these experimentally. We also look at reduction rules for linear boolean-width.
After that we consider cost variants of these parameters, which optimize
a decomposition by means of minimizing the sum of all cut values in a
decomposition rather than taking the maximum. We give a general non-trivial
exact algorithm to compute decompositions with minimal f-cost, for
any cut function f. Finally we evaluate these topics and give suggestions
about what is worth further investigating.