{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:05:38Z","timestamp":1743120338568,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":57,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_59","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:06:22Z","timestamp":1219662382000},"page":"332-339","source":"Crossref","is-referenced-by-count":1,"title":["Branchwidth and Branch Decompositions"],"prefix":"10.1007","author":[{"given":"Illya V.","family":"Hicks","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1_59","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"Proceedings of the 5th Latin American Theoretical Informatics (LATIN 2002). Lecture Notes in Computer Science","author":"J Alber","year":"2002","unstructured":"Alber J, Niedermeier R (2002) Improved tree decomposition based algorithms for\ndomination-like problems. In: Proceedings of the 5th Latin American\nTheoretical Informatics (LATIN 2002). Lecture Notes in Computer Science,\nvol\u00a02286. Springer, Heidelberg, pp 613\u2013627"},{"key":"59_CR2_59","doi-asserted-by":"crossref","unstructured":"Alekhnovich M, Razborov A (2002) Satisfiability, branch-width and tseitin\ntautologies. In: 43rd Annual IEEE Symposium on Foundations of Computer\nScience. IEEE Computer Society, pp 593\u2013603","DOI":"10.1109\/SFCS.2002.1181983"},{"key":"59_CR3_59","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"7","author":"N Alon","year":"1994","unstructured":"Alon N, Seymour PD, Thomas R (1994) Planar separators. SIAM J Discret Math 7:184\u2013193","journal-title":"SIAM J Discret Math"},{"key":"59_CR4_59","unstructured":"Archdeacon D (1980) A\u00a0Kuratowski Theorem for the Projective Plane. PhD thesis, Ohio State University"},{"issue":"2","key":"59_CR5_59","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0095-8956(89)90043-9","volume":"46","author":"D Archdeacon","year":"1989","unstructured":"Archdeacon D, Huneke P (1989) A\u00a0Kuratowski theorem for non-orientable\nsurfaces. J\u00a0Combin Theory Ser B 46(2):173\u2013231","journal-title":"J Combin Theory Ser B"},{"key":"59_CR6_59","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable\ngraphs. J\u00a0Algorithms 12:308\u2013340","journal-title":"J Algorithms"},{"key":"59_CR7_59","first-page":"1","volume":"11","author":"H Bodlaender","year":"1993","unstructured":"Bodlaender H (1993) A\u00a0tourist guide through treewidth. Acta Cybernetica 11:1\u201321","journal-title":"Acta Cybernetica"},{"key":"59_CR8_59","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender H (1996) A\u00a0linear time algorithm for finding tree-decompositions of\nsmall treewidth. SIAM J Comput 25:1305\u20131317","journal-title":"SIAM J Comput"},{"key":"59_CR9_59","first-page":"29","volume-title":"Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS'97. Lecture Notes in Computer Science","author":"H Bodlaender","year":"1997","unstructured":"Bodlaender H (1997) Treewidth: Algorithmic techniques and\nresults. In: Privara I, Rvzicka P (eds) Proceedings of the 22nd International\nSymposium on Mathematical Foundations of Computer Science, MFCS'97. Lecture\nNotes in Computer Science, vol\u00a01295. Springer, Berlin, pp 29\u201336"},{"key":"59_CR10_59","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender H (1998) A\u00a0partial k-arboretum of graphs with bounded treewidth. Theoret Comput Sci 209:1\u201345","journal-title":"Theoret Comput Sci"},{"key":"59_CR11_59","first-page":"1","volume-title":"Proceedings 17th International Workshop on Graph-Theoretic Concepts in Computer Science WG 1991. Lecture Notes in Computer Science","author":"H Bodlaender","year":"1992","unstructured":"Bodlaender H, Gilbert J, Hafsteinsson H, Kloks T (1992) Approximation\ntreewidth, pathwidth, and minimum elimination tree height. In: Schmidt G,\nBerghammer R (eds) Proceedings 17th International Workshop on Graph-Theoretic\nConcepts in Computer Science WG 1991. Lecture Notes in Computer Science, vol\u00a0570. Springer, Berlin, pp 1\u201312"},{"key":"59_CR12_59","first-page":"116","volume-title":"Proceedings Third International Symposium on Algorithms and Computation, ISAAC 1992. Lecture Notes in Computer Science","author":"H Bodlaender","year":"1992","unstructured":"Bodlaender H, Kloks T (1992) Approximating treewidth and pathwidth of some\nclasses of perfect graphs. In: Proceedings Third International Symposium on\nAlgorithms and Computation, ISAAC 1992. Lecture Notes in Computer\n\t  Science, vol\u00a0650. Springer, Berlin, pp 116\u2013125"},{"key":"59_CR13_59","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender H, Kloks T (1996) Efficient and constructive algorithms for the\npathwidth and treewidth of graphs. J\u00a0Algorithms 21:358\u2013402","journal-title":"J Algorithms"},{"issue":"5","key":"59_CR14_59","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender H, Kloks T, Kratsch D, Muller H (1998) Treewidth and minimum\nfill-in on d-trapezoid graphs. J\u00a0Graph Algorithms Appl 2(5):1\u201323","journal-title":"J Graph Algorithms Appl"},{"key":"59_CR15_59","doi-asserted-by":"crossref","unstructured":"Bodlaender H, Tan R, Thilikos D, van Leeuwen J (1997) On interval routing\nschemes and treewidth. Inf Comput 139:92\u2013109","DOI":"10.1006\/inco.1997.2669"},{"key":"59_CR16_59","first-page":"627","volume-title":"Lecture Notes in Computer Science: Proceedings of the 24th International Colloquium on Automata, Languages, and Programming","author":"H Bodlaender","year":"1997","unstructured":"Bodlaender H, Thilikos D (1997) Constructive linear time\nalgorithms for branchwidth. In: Degano P, Gorrieri R, Marchetti-Spaccamela A\n(eds) Lecture Notes in Computer Science: Proceedings of the 24th International\nColloquium on Automata, Languages, and Programming. Springer,\nBerlin, pp 627\u2013637"},{"key":"59_CR17_59","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/jagm.1999.1011","volume":"32","author":"H Bodlaender","year":"1999","unstructured":"Bodlaender H, Thilikos D (1999) Graphs with branchwidth at most three. J\u00a0Algorithms 32:167\u2013194","journal-title":"J Algorithms"},{"key":"59_CR18_59","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie RB, Parker RG, Tovey CA (1992) Automatic generation of linear-time\nalgorithms from predicate calculus descriptions of problems on recursively\nconstructed graph families. Algorithmica 7:555\u2013581","journal-title":"Algorithmica"},{"key":"59_CR19_59","unstructured":"Christian WA (2003) Linear-Time Algorithms for Graphs with Bounded\nBranchwidth. PhD thesis, Rice University"},{"key":"59_CR20_59","unstructured":"Cook W, Seymour PD (1994) An algorithm for the ring-router problem. Technical report, Bellcore"},{"issue":"3","key":"59_CR21_59","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W Cook","year":"2003","unstructured":"Cook W, Seymour PD (2003) Tour merging via branch-decomposition. INFORMS J Comput 15(3):233\u2013248","journal-title":"INFORMS J Comput"},{"key":"59_CR22_59","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle B (1990) The monadic second-order logic of graphs I: Recognizable\nsets of finite graphs. Inf Comput 85:12\u201375","journal-title":"Inf Comput"},{"key":"59_CR23_59","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1090\/conm\/197\/02530","volume":"197","author":"JS Dharmatilake","year":"1996","unstructured":"Dharmatilake JS (1996) A\u00a0min-max theorem using matroid separations. Contemp Math 197:333\u2013342","journal-title":"Contemp Math"},{"key":"59_CR24_59","first-page":"168","volume-title":"Proceedings of the Fourthteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD 2003)","author":"F Fomin","year":"2003","unstructured":"Fomin F, Thilikos D (2003) Dominating sets in planar graphs: Branch-width and\nexponential speed-up. In: Proceedings of the Fourthteenth Annual ACM-SIAM\nSymposium on Discrete Algorithms (Baltimore, MD 2003). ACM, New York, pp 168\u2013177"},{"key":"59_CR25_59","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0095-8956(02)00046-1","volume":"88","author":"JF Geelen","year":"2003","unstructured":"Geelen JF, Gerards AMH, Robertson N, Whittle GP (2003) On the excluded minors\nfor the matroids of branch-width k. J\u00a0Combin Theory Ser B 88:261\u2013265","journal-title":"J Combin Theory Ser B"},{"key":"59_CR26_59","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jctb.2001.2082","volume":"84","author":"JF Geelen","year":"2002","unstructured":"Geelen JF, Gerards AMH, Whittle G (2002) Branch width and well-quasi-ordering\nin matroids and graphs. J\u00a0Combin Theory Ser B 84:270\u2013290","journal-title":"J Combin Theory Ser B"},{"key":"59_CR27_59","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0095-8956(79)90022-4","volume":"27","author":"H Glover","year":"1979","unstructured":"Glover H, Huneke P, Wang CS (1979) 103 graphs that are irreducible for the\nprojective plane. J\u00a0Combin Theory Ser B 27:332\u2013370","journal-title":"J Combin Theory Ser B"},{"key":"59_CR28_59","doi-asserted-by":"crossref","unstructured":"Gu QP, Tamaki H (2005) Optimal branch-decomposition of planar graphs in\n$$ o(n^3) $$ time. In: Proceedings of the 31st International Colloquium on\nAutomata, Languages and Programming. LNCS, vol\u00a03580, pp 373\u2013384","DOI":"10.1007\/11523468_31"},{"key":"59_CR29_59","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1006\/jctb.2002.2120","volume":"86","author":"R Hall","year":"2002","unstructured":"Hall R, Oxley J, Semple C, Whittle G (2002) On matroids of branch-width\nthree. J\u00a0Combin Theory Ser B 86:148\u2013171","journal-title":"J Combin Theory Ser B"},{"key":"59_CR30_59","unstructured":"Hicks IV (2000) Branch Decompositions and their Applications. PhD thesis, Rice University"},{"key":"59_CR31_59","first-page":"31","volume":"159","author":"IV Hicks","year":"2002","unstructured":"Hicks IV (2002) Branchwidth heuristics. Congressus Numerantium 159:31\u201350","journal-title":"Congressus Numerantium"},{"issue":"1","key":"59_CR32_59","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.10099","volume":"43","author":"IV Hicks","year":"2004","unstructured":"Hicks IV (2004) Branch decompositions and minor containment. Networks 43(1):1\u20139","journal-title":"Networks"},{"key":"59_CR33_59","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.20050","volume":"45","author":"IV Hicks","year":"2005","unstructured":"Hicks IV (2005) Graphs, branchwidth, and tangles! oh my! Networks 45:55\u201360","journal-title":"Networks"},{"issue":"4","key":"59_CR34_59","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1287\/ijoc.1040.0075","volume":"17","author":"IV Hicks","year":"2005","unstructured":"Hicks IV (2005) Planar branch decompositions I: The ratcatcher. INFORMS J\nComput 17(4):402\u2013412","journal-title":"INFORMS J Comput"},{"issue":"4","key":"59_CR35_59","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1287\/ijoc.1040.0074","volume":"17","author":"IV Hicks","year":"2005","unstructured":"Hicks IV (2005) Planar branch decompositions II: The cycle method. INFORMS J Comput 17(4):413\u2013421","journal-title":"INFORMS J Comput"},{"key":"59_CR36_59","first-page":"1","volume-title":"Tutorials in Operations Research 2005","author":"IV Hicks","year":"2005","unstructured":"Hicks IV, Koster AMCA, Koloto\u011flu E (2005) Branch and tree decomposition\ntechniques for discrete optimization. In: Cole Smith J (ed) Tutorials in\nOperations Research 2005. INFORMS, Hanover, MD, pp 1\u201329"},{"key":"59_CR37_59","doi-asserted-by":"crossref","unstructured":"Hicks IV, McMurray N (2007) The branchwidth of graphs and their cycle\nmatroids. J\u00a0Combin Theory Ser B 97:681\u2013692","DOI":"10.1016\/j.jctb.2006.12.007"},{"key":"59_CR38_59","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd P (2002) On the exclued minors for matroids of branch-width\nthree. preprint","DOI":"10.37236\/1648"},{"key":"59_CR39_59","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/3-540-49116-3_16","volume-title":"STAC'99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 1999 Proceedings","author":"T Kloks","year":"1999","unstructured":"Kloks T, Kratochvil J, M\u00fcller H (1999) New branchwidth territories. In:\nMeinel\u00a0C, Tison S (eds) STAC'99, 16th Annual Symposium on Theoretical Aspects\nof Computer Science, Trier, Germany, March 1999 Proceedings. Springer,\nBerlin, pp 173\u2013183"},{"key":"59_CR40_59","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"A Koster","year":"2002","unstructured":"Koster A, van Hoesel S, Kolen A (2002) Solving partial constraint satisfaction\nproblems with tree-decompositions. Networks 40:170\u2013180","journal-title":"Networks"},{"key":"59_CR41_59","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"AMCA Koster","year":"2001","unstructured":"Koster AMCA, Bodlaender HL, van Hoesel SPM (2001) Treewidth: Computational\nexperiments. Electr Notes Discret Math 8:54\u201357","journal-title":"Electr Notes Discret Math"},{"key":"59_CR42_59","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K Kuratowski","year":"1930","unstructured":"Kuratowski K (1930) Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae 15:271\u2013283","journal-title":"Fundamenta Mathematicae"},{"key":"59_CR43_59","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley JG (1992) Matroid Theory. Oxford University Press, Oxford"},{"key":"59_CR44_59","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0895480195280010","volume":"10","author":"S Ramachandramurthi","year":"1997","unstructured":"Ramachandramurthi S (1997) The structure and number of obstructions to\ntreewidth. SIAM J Discret Math 10:146\u2013157","journal-title":"SIAM J Discret Math"},{"key":"59_CR45_59","first-page":"221","volume-title":"Proceeding of the 24th Annual Association for Computing Machinery Symposium on Theory of Computing","author":"B Reed","year":"1992","unstructured":"Reed B (1992) Finding approximate separators and computing tree width\nquickly. In: Proceeding of the 24th Annual Association for Computing Machinery\nSymposium on Theory of Computing. ACM Press, New York, pp 221\u2013228"},{"key":"59_CR46_59","first-page":"87","volume-title":"Survey in Combinatorics","author":"B Reed","year":"1997","unstructured":"Reed B (1997) Tree width and tangles: A\u00a0new connectivity measure and some\napplications. In: Bailey RA (ed) Survey in Combinatorics. Cambridge\nUniversity Press, Cambridge, pp 87\u2013162"},{"key":"59_CR47_59","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G (1991) TSPLIB\u00a0\u2013 a\u00a0traveling salesman library. ORSA J Comput 3:376\u2013384","journal-title":"ORSA J Comput"},{"key":"59_CR48_59","first-page":"153","volume-title":"Surveys in Combinatorics, London Math Society Lecture Note Series, edition 103","author":"N Robertson","year":"1985","unstructured":"Robertson N, Seymour PD (1985) Graph minors: A\u00a0survey. In: Surveys in\nCombinatorics, London Math Society Lecture Note Series, edition 103. Cambridge University\nPress, Cambridge, pp 153\u2013171"},{"key":"59_CR49_59","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson N, Seymour PD (1991) Graph minors X: Obstructions to\ntree-decompositions. J\u00a0Combin Theory Ser B 52:153\u2013190","journal-title":"J Combin Theory Ser B"},{"key":"59_CR50_59","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1006\/jctb.1994.1007","volume":"60","author":"N Robertson","year":"1994","unstructured":"Robertson N, Seymour PD (1994) Graph minors XI: Circuits on a\u00a0surface. J\u00a0Combin Theory Ser B 60:72\u2013106","journal-title":"J Combin Theory Ser B"},{"key":"59_CR51_59","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson N, Seymour PD (1995) Graph minors XIII: The disjoint paths\nproblem. J\u00a0Combin Theory Ser B 63:65\u2013110","journal-title":"J Combin Theory Ser B"},{"key":"59_CR52_59","doi-asserted-by":"crossref","unstructured":"Seymour P, Thomas R (1993) Graph searching and a\u00a0min-max theorem for\ntree-width. J\u00a0Combin Theory Ser B 58:22\u201333","DOI":"10.1006\/jctb.1993.1027"},{"issue":"2","key":"59_CR53_59","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour PD, Thomas R (1994) Call routing and the ratcatcher. Combinatorica 14(2):217\u2013241","journal-title":"Combinatorica"},{"key":"59_CR54_59","doi-asserted-by":"crossref","unstructured":"Tamaki H (2003) A\u00a0linear time heuristic for the branch-decomposition of planar\ngraphs. Technical Report MPI-I-2003-1-010, Max-Planck-Institut fuer Informatik","DOI":"10.1007\/978-3-540-39658-1_68"},{"issue":"4","key":"59_CR55_59","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle JA, Proskurowski A (1997) Algorithms for vertex partitioning problems on\npartial k-trees. SIAM J Discret Math 10(4):529\u2013550","journal-title":"SIAM J Discret Math"},{"key":"59_CR56_59","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(90)90130-R","volume":"48","author":"R Thomas","year":"1990","unstructured":"Thomas R (1990) A\u00a0Menger-like property of tree-width: The finite case. J\u00a0Combin Theory Ser B 48:67\u201376","journal-title":"J Combin Theory Ser B"},{"key":"59_CR57_59","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"115","author":"K Wagner","year":"1937","unstructured":"Wagner K (1937) Uber eine eigenschaft der ebenen komplexe. Math Annal 115:570\u2013590","journal-title":"Math Annal"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T11:03:32Z","timestamp":1720695812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_59","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}