{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T05:41:42Z","timestamp":1736314902582,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_73","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T11:50:30Z","timestamp":1140177030000},"page":"800-811","source":"Crossref","is-referenced-by-count":14,"title":["Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In"],"prefix":"10.1007","author":[{"given":"Yngve","family":"Villanger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"73_CR1","first-page":"7","volume-title":"UAI 2001: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence","author":"E. Amir","year":"2001","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: UAI 2001: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pp. 7\u201315. Morgan Kaufmann Publishers Inc., San Francisco (2001)"},{"key":"73_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."},{"issue":"3","key":"73_CR3","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. Foundations Comp. Sci.\u00a011(3), 397\u2013403 (2000)","journal-title":"Int. J. Foundations Comp. Sci."},{"key":"73_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 Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"2-3","key":"73_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0166-218X(03)00440-2","volume":"136","author":"V. Bouchitt\u00e9","year":"2004","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximations. Discrete Appl. Math.\u00a0136(2-3), 183\u2013196 (2004)","journal-title":"Discrete Appl. Math."},{"key":"73_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."},{"issue":"1-2","key":"73_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. Comput. Sci.\u00a0276(1-2), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"73_CR8","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. Comput.\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"73_CR9","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 - 2\/(k+ 1))n algorithm for k-sat based on local search. Theor. Comput. Sci.\u00a0289(1), 69\u201383 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"73_CR10","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":"73_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":"73_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math.\u00a010, 196\u2013210 (1962)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"73_CR13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.L. Lauritzen","year":"1988","unstructured":"Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their applications to expert systems. J. Royal Statist. Soc., ser B\u00a050, 157\u2013224 (1988)","journal-title":"J. Royal Statist. Soc., ser B"},{"key":"73_CR14","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.: Graph minors II. Algorithmic aspects of tree-width. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"73_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"D.J. Rose","year":"1972","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 183\u2013217. Academic Press, New York (1972)"},{"key":"73_CR16","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 chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"73_CR17","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":"73_CR18","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. Alg. Disc. Meth.\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_73","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T20:07:51Z","timestamp":1736280471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11682462_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}