{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:20:16Z","timestamp":1742912416862,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":29,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"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-30162-4_55","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:37Z","timestamp":1214505397000},"page":"101-105","source":"Crossref","is-referenced-by-count":1,"title":["Branchwidth of Graphs"],"prefix":"10.1007","author":[{"given":"Fedor","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Dimitrios","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1_55","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"55_CR2_55","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability\u00a0\u2013 A\u00a0survey. BIT 25, 2\u201323 (1985)","journal-title":"BIT"},{"key":"55_CR3_55","first-page":"627","volume-title":"Automata, languages and programming (Bologna, 1997). Lecture Notes in Computer Science, vol. 1256","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Constructive linear time algorithms for branchwidth. In: Automata, languages and programming (Bologna, 1997). Lecture Notes in Computer Science, vol.\u00a01256, pp.\u00a0627\u2013637. Springer, Berlin (1997)"},{"key":"55_CR4_55","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/jagm.1999.1011","volume":"32","author":"H.L. Bodlaender","year":"1999","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Graphs with branchwidth at most three. J.\u00a0Algorithms 32, 167\u2013194 (1999)","journal-title":"J. Algorithms"},{"key":"55_CR5_55","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, P.D.: Tour merging via branch\u2011decomposition. Inf. J.\u00a0Comput. 15, 233\u2013248 (2003)","journal-title":"Inf. J. Comput."},{"key":"55_CR6_55","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18, 501\u2013511 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"55_CR7_55","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D.\u00a0M.: Approximation algorithms for classes of graphs excluding single\u2010crossing graphs as minors. J.\u00a0Comput. Syst. Sci. 69, 166\u2013195 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"55_CR8_55","first-page":"631","volume-title":"Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2008)","author":"F. Dorn","year":"2006","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential algorithms for non-local problems on H-minor-free graphs. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2008). pp. 631\u2013640. Society for Industrial and Applied Mathematics, Philadelphia (2006)"},{"key":"55_CR9_55","first-page":"280","volume-title":"Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol. 4168","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol.\u00a04168 , pp.\u00a0280\u2013291. Springer, Berlin (2006)"},{"key":"55_CR10_55","volume-title":"Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science. Springer, Berlin (2005)"},{"key":"55_CR11_55","first-page":"95","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol. 3669","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol.\u00a03669, pp.\u00a095\u2013106. Springer, Berlin (2005)"},{"key":"55_CR12_55","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999)"},{"key":"55_CR13_55","first-page":"563","volume-title":"Proceedings of the 37th annual ACM Symposium on Theory of computing (STOC 2005)","author":"U. Feige","year":"2005","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum\u2010weight vertex separators. In: Proceedings of the 37th annual ACM Symposium on Theory of computing (STOC 2005), pp.\u00a0563\u2013572. ACM Press, New York (2005)"},{"key":"55_CR14_55","first-page":"374","volume-title":"Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Lecture Notes Computer Science, vol. 3787","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. In: Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Lecture Notes Computer Science, vol.\u00a03787, pp.\u00a0374\u2013384. Springer, Berlin (2005)"},{"key":"55_CR15_55","first-page":"581","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes Computer Science, vol. 3142","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes Computer Science, vol.\u00a03142, pp.\u00a0581\u2013592. Springer, Berlin (2004)"},{"key":"55_CR16_55","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput. 36, 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"55_CR17_55","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J.\u00a0Graph Theor. 51, 53\u201381 (2006)","journal-title":"J. Graph Theor."},{"key":"55_CR18_55","first-page":"373","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes Computer Science, vol. 3580","author":"Q.P. Gu","year":"2005","unstructured":"Gu, Q.P., Tamaki, H.: Optimal branch\u2010decomposition of planar graphs in O(n\n                3) time. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes Computer Science, vol.\u00a03580, pp.\u00a0373\u2013384. Springer, Berlin (2005)"},{"key":"55_CR19_55","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2005.08.005","volume":"96","author":"Q.P. Gu","year":"2006","unstructured":"Gu, Q.P., Tamaki, H.: Branch-width, parse trees, and monadic second-order logic for matroids. J.\u00a0Combin. Theor. Ser. B 96, 325\u2013351 (2006)","journal-title":"J. Combin. Theor. Ser. B"},{"key":"55_CR20_55","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.dam.2004.01.015","volume":"145","author":"T. Kloks","year":"2005","unstructured":"Kloks, T., Kratochv\u00edl, J., M\u00fcller, H.: Computing the branchwidth of interval graphs. Discret. Appl. Math. 145, 266\u2013275 (2005)","journal-title":"Discret. Appl. Math."},{"key":"55_CR21_55","doi-asserted-by":"crossref","unstructured":"Mazoit, F.: The branch-width of circular-arc graphs. In: 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), 2006, pp.\u00a0727\u2013736","DOI":"10.1007\/11682462_66"},{"key":"55_CR22_55","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S.I. Oum","year":"2006","unstructured":"Oum, S.I., Seymour, P.: Approximating clique-width and branch-width. J.\u00a0Combin. Theor. Ser. B 96, 514\u2013528 (2006)","journal-title":"J. Combin. Theor. Ser. B"},{"key":"55_CR23_55","first-page":"205","volume-title":"Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG 2006). Lecture Notes Computer Science, vol. 4271","author":"C. Paul","year":"2006","unstructured":"Paul, C., Proskurowski, A., Telle, J.A.: Generating graphs of bounded branchwidth. In: Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG 2006). Lecture Notes Computer Science, vol.\u00a04271, pp.\u00a0205\u2013216. Springer, Berlin (2006)"},{"key":"55_CR24_55","doi-asserted-by":"crossref","unstructured":"Paul, C., Telle, J.A.: New tools and simpler algorithms for branchwidth. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), 2005 pp.\u00a0379\u2013390","DOI":"10.1007\/11561071_35"},{"key":"55_CR25_55","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N. Seymour, P.D.: Graph minors. X. Obstructions to tree\u2010decomposition J.\u00a0Combin. Theor. Ser. B 52, 153\u2013190 (1991)","journal-title":"Combin. Theor. Ser. B"},{"key":"55_CR26_55","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1006\/jctb.1995.1034","volume":"64","author":"N. Robertson","year":"1995","unstructured":"Robertson, N. Seymour, P.D.: Graph minors. XII. Distance on a\u00a0surface. J.\u00a0Combin. Theor. Ser. B 64, 240\u2013272 (1995)","journal-title":"J. Combin. Theor. Ser. B"},{"issue":"1","key":"55_CR27_55","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N. Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J.\u00a0Combin. Theor. Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theor. B"},{"key":"55_CR28_55","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a\u00a0planar graph. J.\u00a0Combin. Theor. Ser. B 62, 323\u2013348 (1994)","journal-title":"J. Combin. Theor. Ser. B"},{"key":"55_CR29_55","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14, 217\u2013241 (1994)","journal-title":"Combinatorica"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:05:27Z","timestamp":1662170727000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_55"}},"subtitle":["2003; Fomin, Thilikos"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_55","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}