Variations on Boolean-width

Abstract

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.