Practical algorithms for linear boolean-width

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

doi:10.4230/LIPIcs.IPEC.2015.187

Practical algorithms for linear boolean-width

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

Algorithms

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	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	187-198
Number of pages	12
Volume	43
ISBN (Electronic)	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 number: 10 http://algo2015.upatras.gr/ipec

Conference

Conference	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Abbreviated title	IPEC 2015
Country/Territory	Greece
City	Patras
Period	16/09/15 → 18/09/15
Internet address	http://algo2015.upatras.gr/ipec

Keywords

Boolean-width
Exact algorithms
Graph decomposition
Heuristics
Vertex subset problems

Access to Document

10.4230/LIPIcs.IPEC.2015.187

Cite this

@inproceedings{c1163c4ab0a245e3b2a0d2d8019ec99a,

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}, C.B. and {van Houten}, F.J.P. and H.L. Bodlaender",

year = "2015",

month = nov,

day = "1",

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

language = "English",

volume = "43",

pages = "187--198",

booktitle = "10th International Symposium on Parameterized and Exact Computation, IPEC 2015",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

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

url = "http://algo2015.upatras.gr/ipec",

}

ten Brinke, CB, van Houten, FJP & Bodlaender, HL 2015, Practical algorithms for linear boolean-width. in 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. vol. 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 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, C.B.; van Houten, F.J.P.; Bodlaender, H.L.
10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Vol. 43 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 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, C.B.

AU - van Houten, F.J.P.

AU - Bodlaender, H.L.

N1 - Conference code: 10

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

VL - 43

SP - 187

EP - 198

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

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

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

Other files and links

Fingerprint

Cite this