×

zbMATH — the first resource for mathematics

A combinatorial optimization algorithm for solving the branchwidth problem. (English) Zbl 1241.90121
Summary: We consider the problem of computing an optimal branch decomposition of a graph. Branch decompositions and branchwidth were introduced by Robertson and Seymour in their series of papers that proved the Graph Minors Theorem. Branch decompositions have proven to be useful in solving many NP-hard problems, such as the traveling salesman, independent set, and ring routing problems, by means of combinatorial algorithms that operate on branch decompositions. We develop an implicit enumeration algorithm for the optimal branch decomposition problem and examine its performance on a set of classical graph instances.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308–340 (1991) · Zbl 0734.68073
[2] Bian, Z., Gu, Q., Marzban, M., Tamaki, H., Yoshitake, Y.: Empirical study on branchwidth and branch decomposition of planar graphs. In: Proceedings of the 2008 SIAM Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 152–165. SIAM, Philadelphia (2008)
[3] Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol. 4168, pp. 672–683. Springer, Berlin (2006) · Zbl 1131.68481
[4] Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. J. Graph Algorithms Appl. 10(1), 5–49 (2006) · Zbl 1161.68644
[5] Cook, W.J., Seymour, P.D.: An algorithm for the ring-router problem. Technical report, Bellcore (1994)
[6] Cook, W.J., Seymour, P.D.: Tour merging via branch-decomposition. INFORMS J. Comput. 15(3), 233–248 (2003) · Zbl 1238.90128
[7] Courcelle, B.: The monadic second-order logic of graphs I: recognizable set of finite graphs. Inf. Comput. 85, 12–75 (1990) · Zbl 0722.03008
[8] Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Lecture Notes in Computer Science, vol. 2996, pp. 56–67. Springer, Berlin (2004) · Zbl 1122.68480
[9] Fomin, F.V., Fraigniaud, P., Thilikos, D.M.: The price of connectedness in expansions. Technical Report 273, Department of Informatics, University of Bergen, Bergen, Norway, May 2004
[10] Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. Discrete Appl. Math. 157(12), 2726–2736 (2009) · Zbl 1211.05163
[11] Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34, 477–495 (1978) · Zbl 0385.05048
[12] Hicks, I.V.: Branchwidth heuristics. Congr. Numer. 159, 31–50 (2002) · Zbl 1060.68086
[13] Hicks, I.V.: Branch decompositions and minor containment. Networks 43(1), 1–9 (2004) · Zbl 1031.05121
[14] Hicks, I.V.: Graphs, branchwidth, and tangles! Oh my! Networks 45(2), 55–60 (2005) · Zbl 1067.68103
[15] Hicks, I.V.: Planar branch decompositions II: the cycle method. INFORMS J. Comput. 17(4), 413–421 (2005) · Zbl 1239.05177
[16] Monien, B.: The bandwidth minimization problem for caterpillars with hair length 3 is NP-Complete. SIAM J. Algebr. Discrete Methods 7, 505–512 (1986) · Zbl 0624.68059
[17] Robertson, N., Seymour, P.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52, 153–190 (1991) · Zbl 0764.05069
[18] Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B 63, 65–110 (1995) · Zbl 0823.05038
[19] 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.