LIPIcs.IPEC.2015.187.pdf
- Filesize: 0.59 MB
- 12 pages
Document
Practical Algorithms for Linear Boolean-width
Authors
-
Part of:
Volume:
10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-11-19
Cite AsGet BibTex
Chiel B. ten Brinke, Frank J. P. van Houten, and Hans L. Bodlaender. Practical Algorithms for Linear Boolean-width. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.187
https://doi.org/10.4230/LIPIcs.IPEC.2015.187
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
- graph decomposition
- boolean-width
- heuristics
- exact algorithms
- vertex subset problems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
R. Belmonte and M. Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science, 511:54-65, 2013. Exact and Parameterized Computation.
-
B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle. Boolean-width of graphs. In IWPEC 2009, volume 5917 of LNCS, pages 61-74. Springer, 2009.
-
B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science, 511:66-76, 2013.
-
P. Erdös and A. Rényi. On random graphs. Publicationes Mathematicae 6: 290–297, 1959.
-
E. M. Hvidevold, S. Sharmin, J. A. Telle, and M. Vatshelle. Finding good decompositions for dynamic programming on dense graphs. In IWPEC 2012, volume 7112 of LNCS, pages 219-231. Springer, 2012.
-
K. H. Kim. Boolean Matrix Theory and its Applications. Marcel Dekker, 1982.
-
F. Manne and S. Sharmin. Efficient counting of maximal independent sets in sparse graphs. In Experimental Algorithms, volume 7933 of LNCS, pages 103-114. Springer, 2013.
-
Y. Rabinovich, J. A. Telle, and M. Vatshelle. Upper bounds on boolean-width with applications to exact algorithms. In IWPEC 2013, volume 8246 of LNCS, pages 308-320. Springer, 2013.
-
N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39-61, 1983.
-
S. Sharmin. Practical Aspects of the Graph Parameter Boolean-width. PhD thesis, University of Bergen, Norway, 2014.
-
J. A. Telle. Complexity of domination-type problems in graphs. Nordic Journal of Computing, 1(1):157-171, 1994.
-
Ch. B. Ten Brinke, F. J. P. van Houten, and H. L. Bodlaender. Practical Algorithms for Linear Boolean-width. ArXiv e-prints ArXiV:1509.07687, 2015.
-
Treewidthlib. http://www.staff.science.uu.nl/∼bodla101/treewidthlib/. A benchmark for algorithms for treewidth and related graph problems.
-
F. J. P. van Houten. Experimental research and algorithmic improvements involving the graph parameter boolean-width. Master’s thesis, Utrecht University, The Netherlands, 2015.
-
J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Algorithms - ESA 2009, volume 5757 of LNCS, pages 566-577. Springer, 2009.
-
M. Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, Norway, 2012.