{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:38Z","timestamp":1761621038743,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-010-9421-1","type":"journal-article","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T15:34:07Z","timestamp":1277912047000},"page":"817-838","source":"Crossref","is-referenced-by-count":10,"title":["Faster Parameterized Algorithms for Minimum Fill-in"],"prefix":"10.1007","volume":"61","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,7,1]]},"reference":[{"key":"9421_CR1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/S1571-0653(05)80065-4","volume":"8","author":"A. Berry","year":"2001","unstructured":"Berry, A., Bordat, J.: Moplex elimination orderings. Electron. Notes Discrete Math. 8, 6\u20139 (2001)","journal-title":"Electron. Notes Discrete Math."},{"key":"9421_CR2","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.disc.2005.12.002","volume":"306","author":"A. Berry","year":"2006","unstructured":"Berry, A., Heggernes, P., Villanger, Y.: A vertex incremental approach for maintaining chordality. Discrete Math. 306, 318\u2013336 (2006)","journal-title":"Discrete Math."},{"key":"9421_CR3","doi-asserted-by":"crossref","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. 276, 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9421_CR4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Math. 9, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"key":"9421_CR5","doi-asserted-by":"crossref","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. Inf. Process. Lett. 58, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9421_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1006\/jctb.1994.1056","volume":"31","author":"F.R.K. Chung","year":"1994","unstructured":"Chung, F.R.K., Mumford, D.: Chordal completions of planar graphs. J. Comb. Theory, Ser. B 31, 96\u2013106 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9421_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hamb. 25, 71\u201376 (1961)","journal-title":"Abh. Math. Semin. Univ. Hamb."},{"key":"9421_CR8","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":"9421_CR9","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"key":"9421_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/978-3-540-70575-8_18","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Villanger, Y.: Treewidth computation and extremal combinatorics. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008. Lecture Notes in Computer Science, vol. 5125, pp. 210\u2013221. Springer, Berlin (2008)"},{"issue":"3","key":"9421_CR11","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38(3), 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"key":"9421_CR12","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"9421_CR13","doi-asserted-by":"crossref","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, Ser. B 16, 47\u201356 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9421_CR14","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":"9421_CR15","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: a survey. Discrete Math. 306, 297\u2013317 (2006)","journal-title":"Discrete Math."},{"key":"9421_CR16","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science, FOCS\u201994","author":"H. Kaplan","year":"1994","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mapping. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, FOCS\u201994, pp. 780\u2013791. IEEE Comput. Sci., Los Alamitos (1994)"},{"key":"9421_CR17","doi-asserted-by":"crossref","first-page":"1906\u20131922","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. 28, 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"key":"9421_CR18","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. R. Stat. Soc., Ser. B 50, 157\u2013224 (1988)","journal-title":"J. R. Stat. Soc., Ser. B"},{"key":"9421_CR19","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math. 51, 45\u201364 (1962)","journal-title":"Fundam. Math."},{"key":"9421_CR20","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1137\/S0097539798336073","volume":"30","author":"A. Natanzon","year":"2000","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput. 30, 1067\u20131079 (2000)","journal-title":"SIAM J. Comput."},{"key":"9421_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9421_CR22","doi-asserted-by":"crossref","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. 79, 171\u2013188 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9421_CR23","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D.J. Rose","year":"1970","unstructured":"Rose, D.J.: Triangulated graphs and the elimination process. J. Math. Anal. Appl. 32, 597\u2013609 (1970)","journal-title":"J. Math. Anal. Appl."},{"key":"9421_CR24","doi-asserted-by":"crossref","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. 13, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"9421_CR25","unstructured":"Walter, J.: Representations of rigid cycle graphs. Ph.D. thesis, Wayne State University, USA, 1972"},{"key":"9421_CR26","doi-asserted-by":"crossref","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 2, 77\u201379 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9421-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9421-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9421-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T10:53:55Z","timestamp":1740221635000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9421-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,1]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9421"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9421-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2010,7,1]]}}}