{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:55:47Z","timestamp":1725512147403},"publisher-location":"Berlin, Heidelberg","reference-count":84,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540729181"},{"type":"electronic","value":"9783540729518"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72951-8_3","type":"book-chapter","created":{"date-parts":[[2007,7,2]],"date-time":"2007-07-02T00:03:25Z","timestamp":1183334605000},"page":"11-25","source":"Crossref","is-referenced-by-count":15,"title":["Treewidth: Structure and Algorithms"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","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 \u2013 A survey. BIT\u00a025, 2\u201323 (1985)","journal-title":"BIT"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"Arnborg, S., et al.: An algebraic theory of graph reduction. J. ACM\u00a040, 1134\u20131164 (1993)","journal-title":"J. ACM"},{"key":"3_CR4","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.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"Arnborg, S., Proskurowski, A.: Characterization and recognition of partial 3-trees. SIAM J. Alg. Disc. Meth.\u00a07, 305\u2013314 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math.\u00a023, 11\u201324 (1989)","journal-title":"Disc. Appl. Math."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/11775096_24","volume-title":"Algorithmic Aspects in Information and Management","author":"E.H. Bachoore","year":"2006","unstructured":"Bachoore, E.H., Bodlaender, H.L.: A branch and bound algorithm for exact, upper, and lower bounds on treewidth. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 255\u2013266. Springer, Heidelberg (2006)"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Mathematical Systems Theory\u00a020, 83\u2013127 (1987)","journal-title":"Mathematical Systems Theory"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1017\/S0963548302005369","volume":"11","author":"P. Bellenbaum","year":"2002","unstructured":"Bellenbaum, P., Diestel, R.: Two short proofs concerning tree-decompositions. Combinatorics, Probability, and Computing\u00a011, 541\u2013547 (2002)","journal-title":"Combinatorics, Probability, and Computing"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1142\/S0129054100000211","volume":"11","author":"A. Berry","year":"2000","unstructured":"Berry, A., Bordat, J.-P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Found. Computer Science\u00a011, 397\u2013404 (2000)","journal-title":"Int. J. Found. Computer Science"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey). In: Reliability Of Computer And Communication Network. DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, vol.\u00a05, pp. 33\u201349 (1991)","DOI":"10.1090\/dimacs\/005\/02"},{"key":"3_CR12","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comp. Sc.\u00a0209, 1\u201345 (1998)","journal-title":"Theor. Comp. Sc."},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1\u0161, P., et al. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 1\u201314. Springer, Heidelberg (2006)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11841036_60","volume-title":"Algorithms \u2013 ESA 2006","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., et al.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/11561071_36","volume-title":"Algorithms \u2013 ESA 2005","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth lower bounds with brambles. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 391\u2013402. Springer, Heidelberg (2005)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms\u00a021, 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., van de Eijkhof, F.: Pre-processing rules for triangulation of probabilistic networks. Computational Intelligence\u00a021(3), 286\u2013305 (2005)","journal-title":"Computational Intelligence"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/s004530010070","volume":"29","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Parallel algorithms for series parallel graphs and graphs with treewidth two. Algorithmica\u00a029, 543\u2013559 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1006\/inco.1997.2669","volume":"139","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., et al.: On interval routing schemes and treewidth. Information and Computation\u00a0139(1), 92\u2013109 (1997)","journal-title":"Information and Computation"},{"key":"3_CR22","unstructured":"Borie, R.B.: Recursively Constructed Graph Families. PhD thesis, School of Information and Computer Science, Georgia Institute of Technology (1988)"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01293664","volume":"14","author":"R.B. Borie","year":"1995","unstructured":"Borie, R.B.: Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica\u00a014, 123\u2013137 (1995)","journal-title":"Algorithmica"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/0404043","volume":"4","author":"R.B. Borie","year":"1991","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Deterministic decomposition of recursive graph classes. SIAM J. Disc. Math.\u00a04, 481\u2013501 (1991)","journal-title":"SIAM J. Disc. Math."},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput.\u00a031, 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V. Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comp. Sc.\u00a0276, 17\u201332 (2002)","journal-title":"Theor. Comp. Sc."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1051\/ro:2004011","volume":"38","author":"F. Clautiaux","year":"2004","unstructured":"Clautiaux, F., et al.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Operations Research\u00a038, 13\u201326 (2004)","journal-title":"RAIRO Operations Research"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","volume":"4","author":"E.J. Cockayne","year":"1975","unstructured":"Cockayne, E.J., Goodman, S.E., Hedetniemi, S.T.: A linear algorithm for the domination number of a tree. Information Processing Letters\u00a04, 41\u201344 (1975)","journal-title":"Information Processing Letters"},{"key":"3_CR30","first-page":"107","volume":"19A","author":"C.J. Colbourn","year":"1985","unstructured":"Colbourn, C.J., Stewart, L.K.: Dominating cycles in series-parallel graphs. Ars Combinatorica\u00a019A, 107\u2013112 (1985)","journal-title":"Ars Combinatorica"},{"key":"3_CR31","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.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comp. Sc.\u00a0109, 49\u201382 (1993)","journal-title":"Theor. Comp. Sc."},{"key":"3_CR33","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1017\/S1446788700004031","volume":"6","author":"D.E. Daykin","year":"1966","unstructured":"Daykin, D.E., Ng, C.P.: Algorithms for generalized stability numbers of tree graphs. J. Austral. Math. Soc.\u00a06, 89\u2013100 (1966)","journal-title":"J. Austral. Math. Soc."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Unpublished manuscript (2006)","DOI":"10.1093\/comjnl\/bxm033"},{"key":"3_CR35","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N.D. Dendris","year":"1997","unstructured":"Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theor. Comp. Sc.\u00a0172, 233\u2013254 (1997)","journal-title":"Theor. Comp. Sc."},{"key":"3_CR36","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"3_CR37","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R.J. Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel graphs. J. Math. Anal. Appl.\u00a010, 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"3_CR38","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.: The vertex separation and search number of a graph. Information and Computation\u00a0113, 50\u201379 (1994)","journal-title":"Information and Computation"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M.R. Fellows","year":"1987","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive advances in polynomial-time complexity. Information Processing Letters\u00a026, 157\u2013162 (1987)","journal-title":"Information Processing Letters"},{"key":"3_CR40","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM\u00a035, 727\u2013739 (1988)","journal-title":"J. ACM"},{"key":"3_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: D\u00edaz, J., et al. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 568\u2013580. Springer, Heidelberg (2004)"},{"key":"3_CR42","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/333979.333980","volume":"47","author":"M. Franklin","year":"2000","unstructured":"Franklin, M., Galil, Z., Yung, M.: Eavesdropping games: A graph-theoretic approach to privacy in distributed systems. J. ACM\u00a047, 225\u2013243 (2000)","journal-title":"J. ACM"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Series B\u00a016, 47\u201356 (1974)","journal-title":"J. Comb. Theory Series B"},{"key":"3_CR44","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence UAI-04, Arlington, Virginia, USA, pp. 201\u2013208. AUAI Press (2004)"},{"key":"3_CR45","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"3_CR46","series-title":"Lecture Notes in Computer Science","first-page":"373","volume-title":"Automata, Languages and Programming","author":"Q.-P. Gu","year":"2005","unstructured":"Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n 3) time. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"3_CR47","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0304-3975(87)90050-8","volume":"51","author":"A. Habel","year":"1987","unstructured":"Habel, A., Kreowski, H.J.: Characteristics of graph languages generated by edge replacement. Theor. Comp. Sc.\u00a051, 81\u2013115 (1987)","journal-title":"Theor. Comp. Sc."},{"key":"3_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-18771-5_41","volume-title":"Graph-Grammars and Their Application to Computer Science","author":"A. Habel","year":"1987","unstructured":"Habel, A., Kreowski, H.J.: May we introduce to you: hyperedge replacement. In: Ehrig, H., et al. (eds.) Graph Grammars 1986. LNCS, vol.\u00a0291, pp. 15\u201326. Springer, Heidelberg (1987)"},{"key":"3_CR49","volume-title":"Proc. of the Japan-US Joint Seminar on Discrete Algorithms and Complexity","author":"E. Hare","year":"1987","unstructured":"Hare, E., et al.: Linear-time computability of combinatorial problems on generalized-series-parallel graphs. In: Johnson, D.S., et al. (eds.) Proc. of the Japan-US Joint Seminar on Discrete Algorithms and Complexity, Orlando, Florida, Academic Press, London (1987)"},{"key":"3_CR50","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1137\/0607043","volume":"7","author":"R. Hassin","year":"1986","unstructured":"Hassin, R., Tamir, A.: Efficient algorithms for optimization and selection on series-parallel graphs. SIAM J. Alg. Disc. Meth.\u00a07, 379\u2013389 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"3_CR51","first-page":"196","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. SIAM\u00a010, 196\u2013210 (1962)","journal-title":"J. SIAM"},{"key":"3_CR52","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1287\/ijoc.1040.0075","volume":"17","author":"I.V. Hicks","year":"2005","unstructured":"Hicks, I.V.: Planar branch decompositions I: The ratcatcher. INFORMS J. on Computing\u00a017, 402\u2013412 (2005)","journal-title":"INFORMS J. on Computing"},{"key":"3_CR53","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1287\/ijoc.1040.0074","volume":"17","author":"I.V. Hicks","year":"2005","unstructured":"Hicks, I.V.: Planar branch decompositions II: The cycle method. INFORMS J. on Computing\u00a017, 413\u2013421 (2005)","journal-title":"INFORMS J. on Computing"},{"key":"3_CR54","doi-asserted-by":"crossref","unstructured":"Hicks, I.V., Koster, A.M.C.A., Koloto\u011flu, E.: Branch and tree decomposition techniques for discrete optimization. In: Smith, J.C. (ed.) TutORials 2005, INFORMS Annual Meeting. INFORMS Tutorials in Operations Research Series, pp. 1\u201329 (2005)","DOI":"10.1287\/educ.1053.0017"},{"key":"3_CR55","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., et al.: Width parameters beyond tree-width and their applications. Paper to appear in this special issue (2006)","DOI":"10.1016\/j.ejc.2006.06.005"},{"key":"3_CR56","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0166-218X(83)90003-3","volume":"5","author":"T. Kikuno","year":"1983","unstructured":"Kikuno, T., Yoshida, N., Kakuda, Y.: A linear algorithm for the domination number of a series-parallel graph. Disc. Appl. Math.\u00a05, 299\u2013311 (1983)","journal-title":"Disc. Appl. Math."},{"key":"3_CR57","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path width. Information Processing Letters\u00a042, 345\u2013350 (1992)","journal-title":"Information Processing Letters"},{"key":"3_CR58","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L.M. Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Disc. Math.\u00a055, 181\u2013184 (1985)","journal-title":"Disc. Math."},{"key":"3_CR59","volume-title":"Algorithm Design","author":"J. Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Addison-Wesley, Boston (2005)"},{"issue":"3","key":"3_CR60","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S009753979427087X","volume":"27","author":"T. Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D.: Listing all minimal separators of a graph. SIAM J. Comput.\u00a027(3), 605\u2013613 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"3_CR61","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"A.M.C.A. Koster","year":"2002","unstructured":"Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks\u00a040(3), 170\u2013180 (2002)","journal-title":"Networks"},{"key":"3_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/BFb0028596","volume-title":"STACS 98","author":"D. Lapoire","year":"1998","unstructured":"Lapoire, D.: Recognizability equals definability, for every set of graphs of bounded tree-width. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 618\u2013628. Springer, Heidelberg (1998)"},{"key":"3_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-19488-6_128","volume-title":"Automata, Languages and Programming","author":"C. Lautemann","year":"1988","unstructured":"Lautemann, C.: Efficient algorithms on context-free graph languages. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 362\u2013378. Springer, Heidelberg (1988)"},{"key":"3_CR64","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF00289017","volume":"27","author":"C. Lautemann","year":"1990","unstructured":"Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Informatica\u00a027, 399 (1990)","journal-title":"Acta Informatica"},{"key":"3_CR65","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(91)90020-Y","volume":"12","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J., Thomas, R.: Algorithms for finding tree-decompositions of graphs. J. Algorithms\u00a012, 1\u201322 (1991)","journal-title":"J. Algorithms"},{"key":"3_CR66","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Disc. Appl. Math.\u00a079, 171\u2013188 (1997)","journal-title":"Disc. Appl. Math."},{"key":"3_CR67","first-page":"71","volume":"45","author":"J. Pfaff","year":"1984","unstructured":"Pfaff, J., Laskar, R., Hedetniemi, S.T.: Linear algorithms for independent domination and total domination in series-parallel graphs. Congressus Numerantium\u00a045, 71\u201382 (1984)","journal-title":"Congressus Numerantium"},{"key":"3_CR68","series-title":"LMS Lecture Note Series","first-page":"87","volume-title":"Surveys in Combinatorics","author":"B.A. Reed","year":"1997","unstructured":"Reed, B.A.: Tree width and tangles, a new measure of connectivity and some applications. In: Surveys in Combinatorics. LMS Lecture Note Series, vol.\u00a0241, pp. 87\u2013162. Cambridge University Press, Cambridge (1997)"},{"key":"3_CR69","series-title":"CMS Books in Mathematics","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/0-387-22444-0_4","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"B.A. Reed","year":"2003","unstructured":"Reed, B.A.: Algorithmic aspects of tree width. In: Recent Advances in Algorithms and Combinatorics. CMS Books in Mathematics, pp. 85\u2013107. Springer, New York (2003)"},{"key":"3_CR70","unstructured":"Richey, M.B.: Combinatorial optimization on series-parallel graphs: algorithms and complexity. PhD thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (1985)"},{"key":"3_CR71","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"3_CR72","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. Comb. Theory Series B\u00a063, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Series B"},{"key":"3_CR73","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR74","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0895480193243043","volume":"9","author":"D.P. Sanders","year":"1996","unstructured":"Sanders, D.P.: On linear recognition of tree-width at most four. SIAM J. Disc. Math.\u00a09(1), 101\u2013117 (1996)","journal-title":"SIAM J. Disc. Math."},{"key":"3_CR75","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P.D. Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a minimax theorem for tree-width. J. Comb. Theory Series B\u00a058, 239\u2013257 (1993)","journal-title":"J. Comb. Theory Series B"},{"issue":"2","key":"3_CR76","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\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"3_CR77","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0196-6774(02)00225-0","volume":"47","author":"K. Skodinis","year":"2003","unstructured":"Skodinis, K.: Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. J. Algorithms\u00a047, 40\u201359 (2003)","journal-title":"J. Algorithms"},{"issue":"12","key":"3_CR78","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TCS.1984.1085460","volume":"31","author":"M.M. Sys\u0142o","year":"1984","unstructured":"Sys\u0142o, M.M.: Series-parallel graphs and depth-first search trees. IEEE Trans. on Circuits and Systems\u00a031(12), 1029\u20131033 (1984)","journal-title":"IEEE Trans. on Circuits and Systems"},{"key":"3_CR79","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM\u00a029, 623\u2013641 (1982)","journal-title":"J. ACM"},{"key":"3_CR80","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Disc. Math.\u00a010, 529\u2013550 (1997)","journal-title":"SIAM J. Disc. Math."},{"key":"3_CR81","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/11682462_73","volume-title":"LATIN 2006: Theoretical Informatics","author":"Y. Villanger","year":"2006","unstructured":"Villanger, Y.: Improved exponential-time algorithms for treewidth and minimum fill-in. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 800\u2013811. Springer, Heidelberg (2006)"},{"key":"3_CR82","unstructured":"Wimer, T.V.: Linear algorithms for the dominating cycle problems in series-parallel graphs, 2-trees and Halin graphs. Congressus Numerantium\u00a056 (1987)"},{"key":"3_CR83","unstructured":"Wimer, T.V.: Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Computer Science, Clemson University (1987)"},{"key":"3_CR84","first-page":"43","volume":"50","author":"T.V. Wimer","year":"1985","unstructured":"Wimer, T.V., Hedetniemi, S.T., Laskar, R.: A methodology for constructing linear graph algorithms. Congressus Numerantium\u00a050, 43\u201360 (1985)","journal-title":"Congressus Numerantium"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72951-8_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T20:05:42Z","timestamp":1683921942000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72951-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540729181","9783540729518"],"references-count":84,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72951-8_3","relation":{},"subject":[]}}