Practical algorithms for linear boolean-width

Chiel B. Ten Brinke; Frank J P Van Houten; Hans L. Bodlaender

doi:10.4230/LIPIcs.IPEC.2015.187

Practical algorithms for linear boolean-width

Chiel B. Ten Brinke, Frank J P Van Houten, Hans L. Bodlaender

Utrecht University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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 language	English
Title of host publication	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	187-198
Number of pages	12
Volume	43
ISBN (Print)	9783939897927
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2015.187
Publication status	Published - 1 Nov 2015
Event	10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Greece Duration: 16 Sept 2015 → 18 Sept 2015

Conference

Conference	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Country/Territory	Greece
City	Patras
Period	16/09/15 → 18/09/15

Keywords

Boolean-width
Exact algorithms
Graph decomposition
Heuristics
Vertex subset problems

Access to Document

10.4230/LIPIcs.IPEC.2015.187

19Final published version, 607 KBLicence: CC BY

Cite this

@inproceedings{5a98ea4c6f714f9293576f7ad6cad456,

title = "Practical algorithms for linear boolean-width",

abstract = "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.",

keywords = "Boolean-width, Exact algorithms, Graph decomposition, Heuristics, Vertex subset problems",

author = "{Ten Brinke}, {Chiel B.} and {Van Houten}, {Frank J P} and Bodlaender, {Hans L.}",

year = "2015",

month = nov,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2015.187",

language = "English",

isbn = "9783939897927",

volume = "43",

pages = "187--198",

booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

address = "Germany",

note = "10th International Symposium on Parameterized and Exact Computation, IPEC 2015 ; Conference date: 16-09-2015 Through 18-09-2015",

}

Ten Brinke, CB, Van Houten, FJP & Bodlaender, HL 2015, Practical algorithms for linear boolean-width. in Leibniz International Proceedings in Informatics, LIPIcs. vol. 43, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 187-198, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, 16/09/15. https://doi.org/10.4230/LIPIcs.IPEC.2015.187

Practical algorithms for linear boolean-width. / Ten Brinke, Chiel B.; Van Houten, Frank J P; Bodlaender, Hans L.
Leibniz International Proceedings in Informatics, LIPIcs. Vol. 43 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 187-198.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Practical algorithms for linear boolean-width

AU - Ten Brinke, Chiel B.

AU - Van Houten, Frank J P

AU - Bodlaender, Hans L.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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.

AB - 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.

KW - Boolean-width

KW - Exact algorithms

KW - Graph decomposition

KW - Heuristics

KW - Vertex subset problems

UR - http://www.scopus.com/inward/record.url?scp=84958244308&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2015.187

DO - 10.4230/LIPIcs.IPEC.2015.187

M3 - Conference contribution

AN - SCOPUS:84958244308

SN - 9783939897927

VL - 43

SP - 187

EP - 198

BT - Leibniz International Proceedings in Informatics, LIPIcs

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

Y2 - 16 September 2015 through 18 September 2015

ER -

Practical algorithms for linear boolean-width

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this