2026-07-22T03:55:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5582 2024-03-06T10:36:36Z ddc:004 open_access

Practical Algorithms for Linear Boolean-width ten Brinke, Chiel B. van Houten, Frank J. P. Bodlaender, Hans L. graph decomposition boolean-width heuristics exact algorithms vertex subset problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chiel B. ten Brinke and Frank J. P. van Houten and Hans L. Bodlaender 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.187 urn:nbn:de:0030-drops-55821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.187 eng https://creativecommons.org/licenses/by/3.0/legalcode