{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:11:00Z","timestamp":1784110260242,"version":"3.55.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,10,30]],"date-time":"2008-10-30T00:00:00Z","timestamp":1225324800000},"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":[[2010,8]]},"DOI":"10.1007\/s00453-008-9233-8","type":"journal-article","created":{"date-parts":[[2008,10,29]],"date-time":"2008-10-29T18:10:17Z","timestamp":1225303817000},"page":"747-768","source":"Crossref","is-referenced-by-count":74,"title":["Chordal Deletion is Fixed-Parameter Tractable"],"prefix":"10.1007","volume":"57","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,10,30]]},"reference":[{"key":"9233_CR1","first-page":"641","volume-title":"SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"I. Adler","year":"2008","unstructured":"Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 641\u2013650. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"issue":"1\u20132","key":"9233_CR2","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"4","key":"9233_CR3","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(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9233_CR4","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127, 415\u2013429 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9233_CR5","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol. B, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"issue":"3","key":"9233_CR6","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F. Dehne","year":"2007","unstructured":"Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An O(2 O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9233_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/11758471_31","volume-title":"Algorithms and Complexity","author":"M. Dom","year":"2006","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Algorithms and Complexity. Lecture Notes in Computer Science, vol. 3998, pp. 320\u2013331. Springer, Berlin (2006)"},{"key":"9233_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"9233_CR9","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"9233_CR10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02066678","volume":"12","author":"T. Gallai","year":"1961","unstructured":"Gallai, T.: Maximum-minimum S\u00e4tze und verallgemeinerte Faktoren von Graphen. Acta Math. Acad. Sci. Hung. 12, 131\u2013173 (1961)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9233_CR11","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)"},{"issue":"2","key":"9233_CR12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"9233_CR13","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9233_CR14","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/1250790.1250847","volume-title":"STOC \u201907: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion with few edges. In: STOC \u201907: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 374\u2013381. ACM, New York (2007)"},{"key":"9233_CR15","unstructured":"Ho, M.L.: Linear time algorithms for graphs close to chordal graphs. M. Phil. Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong (2003)"},{"issue":"5","key":"9233_CR16","doi-asserted-by":"crossref","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. 28(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9233_CR17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1080\/15427951.2004.10129077","volume":"1","author":"J. Kleinberg","year":"2003","unstructured":"Kleinberg, J.: Detecting a network failure. Internet Math. 1(1), 37\u201355 (2003)","journal-title":"Internet Math."},{"key":"9233_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Lecture Notes in Computer Science, vol.\u00a0842. Springer, Berlin (1994)"},{"issue":"2","key":"9233_CR19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J.\u00a0Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9233_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-540-79723-4_14","volume-title":"Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2008)","author":"D. Lokshtanov","year":"2008","unstructured":"Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2008). Lecture Notes in Computer Science, vol. 5018, pp. 141\u2013147. Springer, Berlin (2008)"},{"issue":"3","key":"9233_CR21","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3), 407\u2013424 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9233_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/978-3-540-74839-7_28","volume-title":"33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007)","author":"D. Marx","year":"2007","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. In: 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). Lecture Notes in Computer Science, vol. 4769, pp. 292\u2013303. Springer, Berlin (2007)"},{"issue":"1","key":"9233_CR23","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A. Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9233_CR24","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9233_CR25","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors, XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"9233_CR26","doi-asserted-by":"crossref","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. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9233_CR27","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. Algebr. Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9233-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9233-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9233-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:02Z","timestamp":1559137502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9233-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,30]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9233"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9233-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,30]]}}}