{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T14:03:27Z","timestamp":1779890607292,"version":"3.53.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,27]],"date-time":"2015-06-27T00:00:00Z","timestamp":1435363200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0014-x","type":"journal-article","created":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T14:01:06Z","timestamp":1435327266000},"page":"118-137","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Chordal Editing is Fixed-Parameter Tractable"],"prefix":"10.1007","volume":"75","author":[{"given":"Yixin","family":"Cao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,27]]},"reference":[{"issue":"4","key":"14_CR1","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","volume":"15","author":"E Balas","year":"1986","unstructured":"Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054\u20131068 (1986). doi: 10.1137\/0215075","journal-title":"SIAM J. Comput."},{"key":"14_CR2","first-page":"155","volume-title":"Graph Theory and Theoretical Physics","author":"C Berge","year":"1967","unstructured":"Berge, C.: Some classes of perfect graphs. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 155\u2013166. Academic Press, New York (1967)"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0012-365X(96)00161-6","volume":"165\u2013166","author":"C Berge","year":"1997","unstructured":"Berge, C.: Motivations and history of some of my conjectures. Discrete Math. 165\u2013166, 61\u201370 (1997). doi: 10.1016\/S0012-365X(96)00161-6","journal-title":"Discrete Math."},{"issue":"4","key":"14_CR4","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). doi: 10.1016\/0020-0190(96)00050-6","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"14_CR5","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(3), 415\u2013429 (2003). doi: 10.1016\/S0166-218X(02)00242-1","journal-title":"Discrete Appl. Math."},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Cao, Y.: Unit interval editing is fixed-parameter tractable. In: Automata, Languages and Programming (ICALP), vol. 9134, pp. 306\u2013317. Springer (2015). doi: 10.1007\/978-3-662-47672-7_25","DOI":"10.1007\/978-3-662-47672-7_25"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: new measure and new structures. Algorithmica (2014). doi: 10.1007\/s00453-014-9904-6","DOI":"10.1007\/s00453-014-9904-6"},{"issue":"3","key":"14_CR8","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0166-218X(88)90075-3","volume":"20","author":"PM Dearing","year":"1988","unstructured":"Dearing, P.M., Shier, D.R., Warner, D.D.: Maximal chordal subgraphs. Discrete Appl. Math. 20(3), 181\u2013190 (1988). doi: 10.1016\/0166-218X(88)90075-3","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"14_CR9","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 25(1), 71\u201376 (1961). doi: 10.1007\/BF02992776","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Undegrad. Texts Comput. Sci. (2013). doi: 10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","volume":"9","author":"P Erd\u0151s","year":"1962","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On the maximal number of disjoint circuits of a graph. Publicationes Mathematicae Debrecen 9, 3\u201312 (1962)","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"14_CR12","first-page":"113","volume":"1","author":"A Hajnal","year":"1958","unstructured":"Hajnal, A., Sur\u00e1nyi, J.: \u00dcber die aufl\u00f6sung von graphen in vollst\u00e4ndige teilgraphen. Annales Universitatis Scientarium Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae Sectio Mathematica 1, 113\u2013121 (1958)","journal-title":"Annales Universitatis Scientarium Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae Sectio Mathematica"},{"key":"14_CR13","doi-asserted-by":"crossref","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. A preliminary version appeared in FOCS 1994 (1999). doi: 10.1137\/S0097539796303044","DOI":"10.1137\/S0097539796303044"},{"issue":"4","key":"14_CR14","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1137\/0208049","volume":"8","author":"MS Krishnamoorthy","year":"1979","unstructured":"Krishnamoorthy, M.S., Deo, N.: Node-deletion NP-complete problems. SIAM J. Comput. 8(4), 619\u2013625 (1979). doi: 10.1137\/0208049","journal-title":"SIAM J. Comput."},{"issue":"6","key":"14_CR15","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.1137\/0910070","volume":"10","author":"JG Lewis","year":"1989","unstructured":"Lewis, J.G., Peyton, B.W., Pothen, A.: A fast algorithm for reordering sparse matrices for parallel factorization. SIAM J. Sci. Stat. Comput. 10(6), 1146\u20131173 (1989). doi: 10.1137\/0910070","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230. Preliminary versions independently presented in STOC 1978 (1980). doi: 10.1016\/0022-0000(80)90060-4","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"14_CR17","unstructured":"Mancini, F.: Graph Modification problems related to graph classes. Ph.D. thesis, University of Bergen, Bergen (2008)"},{"issue":"3","key":"14_CR18","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). doi: 10.1016\/j.tcs.2005.10.008","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"14_CR19","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010). doi: 10.1007\/s00453-008-9233-8","journal-title":"Algorithmica"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30.1\u201330.35. A preliminary version appeared in STACS 2010 (2013). doi: 10.1145\/2500119","DOI":"10.1145\/2500119"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128. A preliminary version appeared in WG 1999 (2001). doi: 10.1016\/S0166-218X(00)00391-7","DOI":"10.1016\/S0166-218X(00)00391-7"},{"issue":"4","key":"14_CR22","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004). doi: 10.1016\/j.orl.2003.10.009","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"14_CR23","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"DJ Rose","year":"1970","unstructured":"Rose, D.J.: Triangulated graphs and the elimination process. J. Math. Anal. Appl. 32(3), 597\u2013609 (1970). doi: 10.1016\/0022-247X(70)90282-9","journal-title":"J. Math. Anal. Appl."},{"key":"14_CR24","first-page":"183","volume-title":"Graph Theory and Computing","author":"DJ Rose","year":"1973","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Reed, R.C. (ed.) Graph Theory and Computing, pp. 183\u2013217. Academic Press, New York (1973)"},{"issue":"2","key":"14_CR25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230240208","volume":"24","author":"J Xue","year":"1994","unstructured":"Xue, J.: Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Networks 24(2), 109\u2013120 (1994). doi: 10.1002\/net.3230240208","journal-title":"Networks"},{"issue":"1","key":"14_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(1), 77\u201379 (1981). doi: 10.1137\/0602010","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-015-0014-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0014-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0014-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T20:27:08Z","timestamp":1691785628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0014-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,27]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["14"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0014-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,27]]}}}