{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T01:12:47Z","timestamp":1791421967265,"version":"4.3.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_49","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"568-580","source":"Crossref","is-referenced-by-count":40,"title":["Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"49_CR1","first-page":"7","volume-title":"Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI 2001)","author":"E. Amir","year":"2001","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI 2001), San Francisco, CA, pp. 7\u201315. Morgan Kaufmann Publishers, San Francisco (2001)"},{"key":"49_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. Algebraic Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"49_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-46784-X_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"1999","unstructured":"Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, p. 167. Springer, Heidelberg (1999)"},{"key":"49_CR4","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":"49_CR5","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. Theoret. Comput. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"49_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/3-540-45471-3_39","volume-title":"Algorithm Theory - SWAT 2002","author":"H.L. Bodlaender","year":"2002","unstructured":"Bodlaender, H.L., Fomin, F.V.: Tree decompositions with small cost. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 378\u2013387. Springer, Heidelberg (2002)"},{"issue":"1","key":"49_CR7","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. on Computing\u00a031(1), 212\u2013232 (2001)","journal-title":"SIAM J. on Computing"},{"issue":"1-2","key":"49_CR8","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. Theoretical Computer Science\u00a0276(1-2), 17\u201332 (2002)","journal-title":"Theoretical Computer Science"},{"key":"49_CR9","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximation. Discr. Appl. Math. (to appear)"},{"key":"49_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett.\u00a058, 171\u2013176 (1996)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"49_CR11","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.: Tour merging via branch-decomposition. INFORMS J. on Computing\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS J. on Computing"},{"key":"49_CR12","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u22122\/(k+1)) n algorithm for k-SAT based on local search. Theoret. Comput. Sci.\u00a0289, 69\u201383 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"49_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"49_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-44634-6_42","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2001","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, pp. 462\u2013470. Springer, Heidelberg (2001)"},{"key":"49_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/3-540-44985-X_2","volume-title":"Algorithm Theory - SWAT 2000","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Coping with the NP-hardness of the graph bandwidth problem. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 10\u201319. Springer, Heidelberg (2000)"},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in, Research Report RR-2004-09, LIFO\u2013University of Orl\u00e9ans (2004)","DOI":"10.1007\/978-3-540-27836-8_49"},{"key":"49_CR17","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":"49_CR18","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math.\u00a010, 196\u2013210 (1962)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"49_CR19","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput.\u00a028, 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theoretical Computer Science\u00a0175, 309\u2013335 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"49_CR21","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. Discrete Appl. Math.\u00a079(1-3), 171\u2013188 (1997)","journal-title":"Discrete Appl. Math."},{"key":"49_CR22","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":"49_CR23","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, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052, 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"49_CR24","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)"},{"key":"49_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:23:58Z","timestamp":1605741838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}