{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:57:44Z","timestamp":1778680664722,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00493-012-2536-z","type":"journal-article","created":{"date-parts":[[2012,6,6]],"date-time":"2012-06-06T22:43:49Z","timestamp":1339022629000},"page":"289-308","source":"Crossref","is-referenced-by-count":37,"title":["Treewidth computation and extremal combinatorics"],"prefix":"10.1007","volume":"32","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,7]]},"reference":[{"key":"2536_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. G. Corneil and A. Proskurowski: Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods 8 (1987), 277\u2013284.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2536_CR2","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C. Beeri","year":"1983","unstructured":"C. Beeri, R. Fagin, D. Maier and M. Yannakakis: On the desirability of acyclic database schemes, J. ACM 30 (1983), 479\u2013513.","journal-title":"J. ACM"},{"key":"2536_CR3","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1142\/S0129054100000211","volume":"11","author":"A. Berry","year":"2000","unstructured":"A. Berry, J. P. Bordat and O. Cogis: Generating all the minimal separators of a graph., Int. J. Found. Comput. Sci. 11 (2000), 397\u2013403.","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2536_CR4","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski and M. Koivisto: The travelling salesman problem in bounded degree graphs, in: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), vol. 5125 of Lecture Notes in Comput. Sci., Springer, 2008, 198\u2013209."},{"key":"2536_CR5","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00224-009-9185-7","volume":"47","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski and M. Koivisto: Trimmed Moebius inversion and graphs of bounded degree, Theory Comput. Syst. 47 (2010), 637\u2013654.","journal-title":"Theory Comput. Syst."},{"key":"2536_CR6","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender: A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25 (1996), 1305\u20131317.","journal-title":"SIAM J. Comput."},{"key":"2536_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H. L. Bodlaender","year":"1998","unstructured":"H. L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth, Theor. Comp. Sci. 209 (1998), 1\u201345.","journal-title":"Theor. Comp. Sci."},{"key":"2536_CR8","unstructured":"H. L. Bodlaender, F. V. Fomin, A. M. C. A. Koster, D. Kratsch and D. M. Thilikos: On exact algorithms for treewidth, in: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), vol. 4168 of Lecture Notes in Comput. Sci., Springer, 2006, 672\u2013683."},{"issue":"3","key":"2536_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H. L. Bodlaender","year":"2008","unstructured":"H. L. Bodlaender and A. M. C. A. Koster: Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51(3), 2008, 255\u2013269.","journal-title":"The Computer Journal"},{"key":"2536_CR10","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s: On generalized graphs, Acta Math. Acad. Sci. Hungar. (1965), 447\u2013452.","DOI":"10.1007\/BF01904851"},{"key":"2536_CR11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"V. Bouchitt\u00e9 and I. Todinca: Treewidth and minimum fill-in: Grouping the minimal separators, SIAM J. Comput. 31 (2001), 212\u2013232.","journal-title":"SIAM J. Comput."},{"key":"2536_CR12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V. Bouchitt\u00e9","year":"2002","unstructured":"V. Bouchitt\u00e9 and I. Todinca: Listing all potential maximal cliques of a graph., Theor. Comput. Sci. 276 (2002), 17\u201332.","journal-title":"Theor. Comput. Sci."},{"key":"2536_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"P. Buneman: A characterization of rigid circuit graphs, Discrete Math. 9 (1974), 205\u2013212.","journal-title":"Discrete Math."},{"key":"2536_CR14","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann and D. Loveland: A machine program for theoremproving, Comm. ACM 5 (1962), 394\u2013397.","journal-title":"Comm. ACM"},{"key":"2536_CR15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis and H. Putnam: A computing procedure for quantification theory, J. ACM 7 (1960), 201\u2013215.","journal-title":"J. ACM"},{"key":"2536_CR16","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y. Dourisboure","year":"2007","unstructured":"Y. Dourisboure and C. Gavoille: Tree-decompositions with bags of small diameter Discrete Mathematics, 307 (2007), 2008\u20132029.","journal-title":"Discrete Mathematics"},{"key":"2536_CR17","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U. Feige","year":"2008","unstructured":"U. Feige, M. Hajiaghayi and J. R. Lee: Improved approximation algorithms for minimum weight vertex separators, SIAM J. Comput. 38 (2008), 629\u2013657.","journal-title":"SIAM J. Comput."},{"key":"2536_CR18","first-page":"47","volume":"87","author":"F. Fomin","year":"2005","unstructured":"F. Fomin, F. Grandoni and D. Kratsch: Some new techniques in design and analysis of exact (exponential) algorithms, Bulletin of the European Association for Theoretical Computer Science 87 (2005), 47\u201377.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"2536_CR19","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch: Exact Exponential Algorithms, Springer, 2010.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"2536_CR20","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming","author":"F. V. Fomin","year":"2004","unstructured":"F. V. Fomin, D. Kratsch and I. Todinca: Exact algorithms for treewidth and minimum fill-in, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), vol. 3142 of Lecture Notes in Comput. Sci., Springer, Berlin, 2004, 568\u2013580."},{"key":"2536_CR21","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F. V. Fomin","year":"2008","unstructured":"F. V. Fomin, D. Kratsch, I. Todinca and Y. Villanger: Exact algorithms for treewidth and minimum fill-in, SIAM J. Comput. 38 (2008), 1058\u20131079.","journal-title":"SIAM J. Comput."},{"key":"2536_CR22","unstructured":"F. V. Fomin and Y. Villanger: Treewidth computation and extremal combinatorics, in: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2008), vol. 5125 of Lecture Notes in Comput. Sci., Springer, 2008, 210\u2013221."},{"key":"2536_CR23","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, (1980)."},{"key":"2536_CR24","volume-title":"Concrete mathematics: A foundation for computer science","author":"R. L. Graham","year":"1994","unstructured":"R. L. Graham, D. E. Knuth and O. Patashnik: Concrete mathematics: A foundation for computer science, Addison-Wesley Publishing Company, Reading, MA, second ed., 1994.","edition":"second ed."},{"key":"2536_CR25","first-page":"196","volume":"10","author":"M. Held","year":"1962","unstructured":"M. Held and R. M. Karp: A dynamic programming approach to sequencing problems, Journal of SIAM 10 (1962), 196\u2013210.","journal-title":"Journal of SIAM"},{"key":"2536_CR26","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C.-W. Ho","year":"1989","unstructured":"C.-W. Ho and R. C. T. Lee: Counting clique trees and computing perfect elimination schemes in parallel, Inform. Process. Lett. 31 (1989), 61\u201368.","journal-title":"Inform. Process. Lett."},{"key":"2536_CR27","first-page":"61","volume":"82","author":"K. Iwama","year":"2004","unstructured":"K. Iwama: Worst-case upper bounds for k-SAT, Bulletin of the European Association for Theoretical Computer Science 82 (2004), 61\u201371.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"2536_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal combinatorics with applications in computer science","author":"S. Jukna","year":"2001","unstructured":"S. Jukna: Extremal combinatorics with applications in computer science, Springer-Verlag, Berlin, 2001."},{"key":"2536_CR29","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S009753979427087X","volume":"27","author":"T. Kloks","year":"1998","unstructured":"T. Kloks and D. Kratsch: Listing all minimal separators of a graph., SIAM J. Comput. 27 (1998), 605\u2013613.","journal-title":"SIAM J. Comput."},{"key":"2536_CR30","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov: On the complexity of computing treelength, in: Proceedings of the 32nd International Symposium Mathematical Foundations of Computer Science (MFCS 2007), vol. 4708 of Lecture Notes in Comput. Sci., Springer, 2007, 276\u2013287.","DOI":"10.1007\/978-3-540-74456-6_26"},{"key":"2536_CR31","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S. Parter","year":"1961","unstructured":"S. Parter: The use of linear graphs in Gauss elimination, SIAM Review 3 (1961), 119\u2013130.","journal-title":"SIAM Review"},{"key":"2536_CR32","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. D. Seymour: Graph minors. II. Algorithmic aspects of treewidth, Journal of Algorithms 7 (1986), 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"2536_CR33","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing, R. C. Read","author":"D. J. Rose","year":"1972","unstructured":"D. J. Rose: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in: Graph Theory and Computing, R. C. Read, ed., Academic Press, New York, 1972, 183\u2013217."},{"key":"2536_CR34","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning: Algorithmics in exponential time, in: Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), vol. 3404 of Lecture Notes in Comput. Sci., Springer, 2005, 36\u201343.","DOI":"10.1007\/978-3-540-31856-9_3"},{"key":"2536_CR35","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/242581.242585","volume":"27","author":"S. Seiden","year":"1996","unstructured":"S. Seiden: Theoretical computer science cheat sheet, SIGACT News 27 (1996), 52\u201361.","journal-title":"SIGACT News"},{"key":"2536_CR36","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R. E. Tarjan","year":"1977","unstructured":"R. E. Tarjan and A. E. Trojanowski: Finding a maximum independent set, SIAM J. Computing 6 (1977), 537\u2013546.","journal-title":"SIAM J. Computing"},{"key":"2536_CR37","doi-asserted-by":"crossref","unstructured":"Y. Villanger: Improved exponential-time algorithms for treewidth and minimum fill-in, in: Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN 2006), vol. 3887 of Lecture Notes in Comput. Sci., Springer, 2006, 800\u2013811.","DOI":"10.1007\/11682462_73"},{"key":"2536_CR38","doi-asserted-by":"crossref","unstructured":"G. Woeginger: Exact algorithms for NP-hard problems: A survey, in: Combinatorial Optimization \u2014 Eureka, You Shrink!, vol. 2570 of Lecture Notes in Comput. Sci., Springer, 2003, 185\u2013207.","DOI":"10.1007\/3-540-36478-1_17"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2536-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-012-2536-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2536-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,29]],"date-time":"2019-06-29T09:38:56Z","timestamp":1561801136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-012-2536-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["2536"],"URL":"https:\/\/doi.org\/10.1007\/s00493-012-2536-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]}}}