{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T22:53:15Z","timestamp":1786143195003,"version":"3.56.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_60","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"672-683","source":"Crossref","is-referenced-by-count":30,"title":["On Exact Algorithms for Treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arie M. C. A.","family":"Koster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"60_CR1","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":"60_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","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. 217\u2013227. Springer, Heidelberg (2005)"},{"key":"60_CR3","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. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theor. Comp. Sci."},{"key":"60_CR4","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":"60_CR5","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":"60_CR6","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":"60_CR7","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. Sci.\u00a0276, 17\u201332 (2002)","journal-title":"Theor. Comp. Sci."},{"key":"60_CR8","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"},{"key":"60_CR9","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. Sci.\u00a0172, 233\u2013254 (1997)","journal-title":"Theor. Comp. Sci."},{"key":"60_CR10","first-page":"47","volume":"87","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bulletin of the EATCS"},{"key":"60_CR11","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":"60_CR12","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":"60_CR13","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":"60_CR14","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput.\u00a016, 486\u2013502 (1987)","journal-title":"SIAM J. Comput."},{"key":"60_CR15","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":"60_CR16","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":"60_CR17","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":"60_CR18","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":"60_CR19","unstructured":"Treewidthlib (2004), \n                    \n                      http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib"},{"key":"60_CR20","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":"60_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_60.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:58Z","timestamp":1619507818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11841036_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}