Practical algorithms for linear boolean-width

C.B. ten Brinke, F.J.P. van Houten, H.L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.

Original languageEnglish
Title of host publication10th International Symposium on Parameterized and Exact Computation, IPEC 2015
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)9783939897927
Publication statusPublished - 1 Nov 2015
Event10th International Symposium on Parameterized and Exact Computation (IPEC 2015) - Patras, Greece
Duration: 16 Sep 201518 Sep 2015
Conference number: 10


Conference10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Abbreviated titleIPEC 2015
Internet address


  • Boolean-width
  • Exact algorithms
  • Graph decomposition
  • Heuristics
  • Vertex subset problems


Dive into the research topics of 'Practical algorithms for linear boolean-width'. Together they form a unique fingerprint.

Cite this