zbMATH — the first resource for mathematics

Practical algorithms for branch-decompositions of planar graphs. (English) Zbl 1326.05035
Summary: Branch-decompositions of graphs have important algorithmic applications. A graph \(G\) of small branchwidth admits efficient algorithms for many NP-hard problems in \(G\). These algorithms usually run in exponential time in the branchwidth and polynomial time in the size of \(G\). It is critical to compute the branchwidth and a branch-decomposition of small width for a given graph in practical applications of these algorithms. It is known that given a planar graph \(G\) and an integer \(\beta\), whether the branchwidth of \(G\) is at most \(\beta\) can be decided in \(O(n^2)\) time, and an optimal branch-decomposition of \(G\) can be computed in \(O(n^3)\) time. In this paper, we report the practical performance of the algorithms for computing the branchwidth/branch-decomposition of planar \(G\) and the heuristics for improving the algorithms.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
Full Text: DOI
[1] Arnborg, S.; Cornell, D.; Proskurowski, A., Complexity of finding embedding in a k-tree, SIAM J. Discrete. Math., 8, 277-284, (1987) · Zbl 0611.05022
[2] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[3] Z. Bian, Q. Gu, Computing branch decompositions of large planar graphs, in: Proc. of the 7th International Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol. 5038, 2008, pp. 87-100.
[4] Z. Bian, Q. Gu, M. Marzban, H. Tamaki, Y. Yoshitake, Empirical study on branchwidth and branch decomposition of planar graphs, in: Proc. of the 9th SIAM Workshop on Algorithm Engineering and Experiments, ALENEX’08, 2008, pp. 152-165.
[5] Bodlaender, H. L., A tourist guide through treewidth, Acta Cybern., 11, 1-21, (1993) · Zbl 0804.68101
[6] Bodlaender, H. L., A linear time algorithm for finding tree-decomposition of small treewidth, SIAM J. Comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[7] H.L. Bodlaender, D. Thilikos, Constructive linear time algorithm for branchwidth, in: Proc. of the 24th International Colloquium on Automata, Languages, and Programming, 1997, pp. 627-637. · Zbl 1401.05277
[8] Demaine, E. D.; Hajiaghayi, M. T., Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, 28, 1, 19-36, (2008) · Zbl 1174.05115
[9] Dorn, F.; Fomin, F. V.; Thilikos, D. M., Subexponential parameterized algorithms, Computer Science Reviews, 2, 1, 29-39, (2008) · Zbl 1302.68340
[10] Feige, U.; Hajiaghayi, M. T.; Lee, J. R., Improved approximation algorithms for minimum weight vertex separators, SIAM J. Comput., 38, 2, 629-657, (2008) · Zbl 1172.68063
[11] Fomin, F. V.; Thilikos, D. M., Dominating sets in planar graphs: branch-width and exponential speed-up, SIAM J. Comput., 36, 2, 281-309, (2006) · Zbl 1114.05072
[12] Fomin, F. V.; Thilikos, D. M., New upper bounds on the decomposability of planar graphs, J. Graph Theory, 51, 1, 53-81, (2006) · Zbl 1085.05049
[13] Gu, Q. P.; Tamaki, H., Optimal branch decomposition of planar graphs in \(O(n^3)\) time, ACM Trans. Algorithms, 4, 3, 1-13, (2008), article No.30
[14] Hicks, I. V., Planar branch decompositions I: the ratcatcher, INFORMS J. Comput., 17, 4, 402-412, (2005) · Zbl 1239.05176
[15] Hicks, I. V., Planar branch decompositions II: the cycle method, INFORMS Journal on Computing, 17, 4, 413-421, (2005) · Zbl 1239.05177
[16] I.V. Hicks, A.M.C.A. Koster, E. Kolotoğlu, Branch and tree decomposition techniques for discrete optimization, in: TutORials in Operation Research: INFORMS-New Orleans 2005, 2005, pp. 1-29.
[17] The LEDA User Manual, Algorithmic Solutions, Version 4.2.1, 2007. http://www.mpi-inf.mpg.de/LEDA/MANUAL/MANUAL.html.
[18] D. Lokshtanov, M. Pilipczuk, An \(O(c^k n)\) 5-approximation algorithm for treewidth, in: Proc. of the 2013 Annual Symposium on Foundation of Computer Science, (FOCS2013), pp. 499-508, 2013.
[19] Marzban, M.; Gu, Q.; Jia, X., Computational study on planar dominating set problem, Theoret. Comput. Sci., 410, 52, 5455-5466, (2009) · Zbl 1192.68488
[20] Mehlhorn, K.; Nöher, S., LEDA: A platform for combinatorial and geometric computing, (1999), Cambridge University Press New York · Zbl 0976.68156
[21] Public Implementation of a Graph Algorithm Library and Editor, 2007. http://pigale.sourceforge.net/.
[22] Reinelt, G., TSPLIB-A traveling salesman library, ORSA J. Comput., 3, 376-384, (1991) · Zbl 0775.90293
[23] Robertson, N.; Seymour, P. D., Graph minors X. obstructions to tree decomposition, J. Combin. Theory Ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[24] Robertson, N.; Seymour, P. D., Graph minors XIII. the disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[25] G. Schaeffer, Random sampling of large planar maps and convex polyhedra, in: Proc. of the 31st Annual ACM Symposium on the Theory of Computing, STOC’99, 1999, pp. 760-769. · Zbl 1345.05105
[26] Seymour, P. D.; Thomas, R., Call routing and the ratcatcher, Combinatorica, 14, 2, 217-241, (1994) · Zbl 0799.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.