{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:54:02Z","timestamp":1773482042340,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":66,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540483816","type":"print"},{"value":"9783540483823","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11917496_1","type":"book-chapter","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T02:16:13Z","timestamp":1161137773000},"page":"1-14","source":"Crossref","is-referenced-by-count":59,"title":["Treewidth: Characterizations, Applications, and Computations"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2004.01.013","volume":"145","author":"J. Alber","year":"2005","unstructured":"Alber, J., Dorn, F., Niedermeier, R.: Experimental evaluation of a tree decomposition based algorithm for vertex cover on planar graphs. Disc. Appl. Math.\u00a0145, 210\u2013219 (2005)","journal-title":"Disc. Appl. Math."},{"key":"1_CR2","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp. 7\u201315 (2001)"},{"key":"1_CR3","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":"1_CR4","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":"1_CR5","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":"1_CR6","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":"1_CR7","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":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/11427186_20","volume-title":"Experimental and Efficient Algorithms","author":"E.H. Bachoore","year":"2005","unstructured":"Bachoore, E.H., Bodlaender, H.L.: New upper bound heuristics for treewidth. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 216\u2013227. Springer, Heidelberg (2005)"},{"key":"1_CR9","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":"1_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0004-3702(00)00075-8","volume":"125","author":"A. Becker","year":"2001","unstructured":"Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence\u00a0125, 3\u201317 (2001)","journal-title":"Artificial Intelligence"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-36379-3_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"2002","unstructured":"Berry, A., Blair, J.R.S., Heggernes, P.: Maximum cardinality search for computing minimal triangulations. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 1\u201312. Springer, Heidelberg (2002)"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0304-3975(99)00126-7","volume":"250","author":"J.R.S. Blair","year":"2001","unstructured":"Blair, J.R.S., Heggernes, P., Telle, J.: A practical algorithm for making filled graphs minimal. Theor. Comp. Sc.\u00a0250, 125\u2013141 (2001)","journal-title":"Theor. Comp. Sc."},{"key":"1_CR13","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":"1_CR14","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"1_CR15","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":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-30577-4_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., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"key":"1_CR17","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., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"1_CR18","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":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-540-30559-0_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: On the Maximum Cardinality Search lower bound for treewidth. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 81\u201392. Springer, Heidelberg (2004)"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.disc.2005.12.017","volume":"306","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. Disc. Math.\u00a0306, 337\u2013350 (2006)","journal-title":"Disc. Math."},{"issue":"3","key":"1_CR21","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., Eijkhof, F.v.d.: Pre-processing rules for triangulation of probabilistic networks. Computational Intelligence\u00a021(3), 286\u2013305 (2005)","journal-title":"Computational Intelligence"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/978-3-540-30140-0_56","volume-title":"Algorithms \u2013 ESA 2004","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 628\u2013639. Springer, Heidelberg (2004)"},{"key":"1_CR23","doi-asserted-by":"crossref","first-page":"5","DOI":"10.7155\/jgaa.00117","volume":"10","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. Journal of Graph Algorithms and Applications\u00a010, 5\u201349 (2006)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM J. Disc. Math.\u00a06, 181\u2013188 (1993)","journal-title":"SIAM J. Disc. Math."},{"key":"1_CR25","volume-title":"Graduate Texts in Mathematics","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. In: Graduate Texts in Mathematics. Springer, New York (1998)"},{"key":"1_CR26","unstructured":"Borie, R.B.: Recursively Constructed Graph Families. PhD thesis, School of Information and Computer Science, Georgia Institute of Technology (1988)"},{"key":"1_CR27","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":"1_CR28","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":"1_CR29","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":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-44867-5_6","volume-title":"Experimental and Efficient Algorithms","author":"F. Clautiaux","year":"2003","unstructured":"Clautiaux, F., Carlier, J., Moukrim, A., N\u00e9gre, S.: New lower and upper bounds for graph treewidth. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 70\u201380. Springer, Heidelberg (2003)"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1051\/ro:2004011","volume":"38","author":"F. Clautiaux","year":"2004","unstructured":"Clautiaux, F., Moukrim, A., N\u00e9gre, S., Carlier, J.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Operations Research\u00a038, 13\u201326 (2004)","journal-title":"RAIRO Operations Research"},{"issue":"3","key":"1_CR32","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-decomposition. INFORMS J. on Computing\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS J. on Computing"},{"key":"1_CR33","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":"1_CR34","first-page":"69","volume":"6","author":"K. Dohmen","year":"2004","unstructured":"Dohmen, K., P\u00f6nitz, A., Tittmann, P.: A new two-variable generalization of the chromatic polynomial. Disc. Math. and Theor. Comp. Sc.\u00a06, 69\u201390 (2004)","journal-title":"Disc. Math. and Theor. Comp. Sc."},{"key":"1_CR35","unstructured":"Eijkhof, F.v.d., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica (to appear)"},{"key":"1_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 568\u2013580. Springer, Heidelberg (2004)"},{"key":"1_CR37","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":"1_CR38","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence UAI 2004, Arlington, Virginia, USA, pp. 201\u2013208. AUAI Press (2004)"},{"key":"1_CR39","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":"1_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-56402-0_35","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K. Jansen","year":"1993","unstructured":"Jansen, K., Scheffler, P.: Generalized coloring for tree-like graphs. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol.\u00a0657, pp. 50\u201359. Springer, Heidelberg (1993)"},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"71","author":"G. Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: \u00dcber die Aufl\u00f6sung der Gleichugen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str\u00f6me gef\u00fchrt wird. Ann. Phys. Chem.\u00a071, 497\u2013508 (1847)","journal-title":"Ann. Phys. Chem."},{"key":"1_CR42","unstructured":"Koster, A.M.C.A.: Frequency Assignment - Models and Algorithms. PhD thesis, Univ. Maastricht, Maastricht, The Netherlands (1999)"},{"key":"1_CR43","first-page":"54","volume-title":"Electronic Notes in Discrete Mathematics","author":"A.M.C.A. Koster","year":"2001","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. In: Broersma, H., Faigle, U., Hurink, J., Pickl, S. (eds.) Electronic Notes in Discrete Mathematics, vol.\u00a08, pp. 54\u201357. Elsevier Science Publishers, Amsterdam (2001)"},{"key":"1_CR44","unstructured":"Koster, A.M.C.A., Marchal, B., van Hoesel, C.P.M.: Local search algorithms for treewidth. Work in progress (2006)"},{"issue":"3","key":"1_CR45","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":"1_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/11427186_11","volume-title":"Experimental and Efficient Algorithms","author":"A.M.C.A. Koster","year":"2005","unstructured":"Koster, A.M.C.A., Wolle, T., Bodlaender, H.L.: Degree-based treewidth lower bounds. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 101\u2013112. Springer, Heidelberg (2005)"},{"key":"1_CR47","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.J. Lauritzen","year":"1988","unstructured":"Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. The Journal of the Royal Statistical Society. Series B (Methodological)\u00a050, 157\u2013224 (1988)","journal-title":"The Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"1_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BFb0026094","volume-title":"CAAP \u201988","author":"C. Lautemann","year":"1988","unstructured":"Lautemann, C.: Decomposition trees: structured graph representation and efficient algorithms. In: Dauchet, M., Nivat, M. (eds.) CAAP 1988. LNCS, vol.\u00a0299, pp. 28\u201339. Springer, Heidelberg (1988)"},{"key":"1_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-19488-6_129","volume-title":"Automata, Languages and Programming","author":"T. Lengauer","year":"1988","unstructured":"Lengauer, T., Wanke, E.: Efficient analysis of graph properties on context-free graph languages. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 379\u2013393. Springer, Heidelberg (1988)"},{"key":"1_CR50","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/S0895480101397773","volume":"16","author":"B. Lucena","year":"2003","unstructured":"Lucena, B.: A new lower bound for tree-width using maximum cardinality search. SIAM J. Disc. Math.\u00a016, 345\u2013353 (2003)","journal-title":"SIAM J. Disc. Math."},{"key":"1_CR51","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":"1_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-59071-4_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Ramachandramurthi","year":"1995","unstructured":"Ramachandramurthi, S.: A lower bound for treewidth and its consequences. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol.\u00a0903, pp. 14\u201325. Springer, Heidelberg (1995)"},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0895480195280010","volume":"10","author":"S. Ramachandramurthi","year":"1997","unstructured":"Ramachandramurthi, S.: The structure and number of obstructions to treewidth. SIAM J. Disc. Math.\u00a010, 146\u2013157 (1997)","journal-title":"SIAM J. Disc. Math."},{"key":"1_CR54","series-title":"LMS Lecture Note Series","first-page":"87","volume-title":"Tree width and tangles, a new measure of connectivity and some applications","author":"B.A. Reed","year":"1997","unstructured":"Reed, B.A.: Tree width and tangles, a new measure of connectivity and some applications. LMS Lecture Note Series, vol.\u00a0241, pp. 87\u2013162. Cambridge University Press, Cambridge (1997)"},{"key":"1_CR55","first-page":"85","volume-title":"CMS Books Math. \/ Ouvrages Math. SMC","author":"B.A. Reed","year":"2003","unstructured":"Reed, B.A.: Algorithmic aspects of tree width. In: CMS Books Math. \/ Ouvrages Math. SMC, vol.\u00a011, pp. 85\u2013107. Springer, New York (2003)"},{"key":"1_CR56","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":"1_CR57","unstructured":"R\u00f6hrig, H.: Tree decomposition: A feasibility study. Master\u2019s thesis, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (1998)"},{"key":"1_CR58","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."},{"key":"1_CR59","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"},{"key":"1_CR60","first-page":"185","volume-title":"Proc. National Conference on Artificial Intelligence (AAAI 1997)","author":"K. Shoikhet","year":"1997","unstructured":"Shoikhet, K., Geiger, D.: A practical algorithm for finding optimal triangulations. In: Proc. National Conference on Artificial Intelligence (AAAI 1997), pp. 185\u2013190. Morgan Kaufmann, San Francisco (1997)"},{"key":"1_CR61","unstructured":"Sys\u0142o, M.M.: NP-complete problems on some tree-structured graphs: A review. In: Nagl, M., Perl, J. (eds.) Proc. WG 1983 International Workshop on Graph Theoretic Concepts in Computer Science, Linz, West Germany, pp. 342\u2013353. University Verlag Rudolf Trauner (1983)"},{"key":"1_CR62","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"1_CR63","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":"1_CR64","unstructured":"Wimer, T.V.: Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Computer Science, Clemson University (1987)"},{"key":"1_CR65","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"},{"key":"1_CR66","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s004530010017","volume":"27","author":"X. Zhou","year":"2000","unstructured":"Zhou, X., Fuse, K., Nishizeki, T.: A linear algorithm for finding [g,f]-colorings of partial k-trees. Algorithmica\u00a027, 227\u2013243 (2000)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11917496_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:42:27Z","timestamp":1619494947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11917496_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540483816","9783540483823"],"references-count":66,"URL":"https:\/\/doi.org\/10.1007\/11917496_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}