{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:41Z","timestamp":1761621101847},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,5,30]],"date-time":"2012-05-30T00:00:00Z","timestamp":1338336000000},"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":[[2013,4]]},"DOI":"10.1007\/s00453-012-9661-3","type":"journal-article","created":{"date-parts":[[2012,5,29]],"date-time":"2012-05-29T19:07:29Z","timestamp":1338318449000},"page":"845-867","source":"Crossref","is-referenced-by-count":25,"title":["Proper Interval Vertex Deletion"],"prefix":"10.1007","volume":"65","author":[{"given":"Pim","family":"van \u2019t Hof","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,5,30]]},"reference":[{"issue":"2\u20133","key":"9661_CR1","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0166-218X(02)00571-1","volume":"129","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Dragan, F.F.: On linear and circular structure of (claw, net)-free graphs. Discrete Appl. Math. 129(2\u20133), 285\u2013303 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9661_CR2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"issue":"4","key":"9661_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":"9661_CR4","series-title":"Lecture Notes in Computer Science","first-page":"93","volume-title":"Proceedings SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Proceedings SWAT 2010. Lecture Notes in Computer Science, vol. 6139, pp. 93\u2013104. Springer, Berlin (2010)"},{"issue":"5","key":"9661_CR5","doi-asserted-by":"crossref","first-page":"21:1","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J. Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21:1\u201321:19 (2008)","journal-title":"J. ACM"},{"issue":"40\u201342","key":"9661_CR6","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9661_CR7","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/B978-0-444-88074-1.50010-X","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (B)","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (B), pp. 193\u2013242 (1990)"},{"issue":"2","key":"9661_CR8","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X. Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390\u2013403 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9661_CR9","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"9661_CR10","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":"9661_CR11","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume-title":"Topics on Perfect Graphs","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a021, pp. 325\u2013356 (1984)"},{"key":"9661_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/978-3-642-22953-4_21","volume-title":"Proceedings FCT 2011","author":"P. Heggernes","year":"2011","unstructured":"Heggernes, P., van \u2019t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.V.: Parameterized complexity of vertex deletion into perfect graph classes. In: Proceedings FCT 2011. Lecture Notes in Computer Science, vol. 6914, pp. 240\u2013251 (2011)"},{"issue":"5","key":"9661_CR13","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."},{"key":"9661_CR14","first-page":"382","volume-title":"Proceedings STOC 2007","author":"K. Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: Proceedings STOC 2007, pp. 382\u2013390. ACM, New York (2007)"},{"key":"9661_CR15","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."},{"issue":"2","key":"9661_CR16","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":"9661_CR17","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 IWPEC 2008","author":"D. Lokshtanov","year":"2008","unstructured":"Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: Proceedings IWPEC 2008. Lecture Notes in Computer Science, vol. 5018, pp. 141\u2013147. Springer, Berlin (2008)"},{"issue":"4","key":"9661_CR18","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)","journal-title":"Algorithmica"},{"issue":"3\u20134","key":"9661_CR19","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D. Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica 62(3\u20134), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"9661_CR20","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, San Diego (1969)"},{"issue":"2","key":"9661_CR21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"9661_CR22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0012-365X(74)80027-0","volume":"7","author":"A. Tucker","year":"1974","unstructured":"Tucker, A.: Structure theorems for some circular-arc graphs. Discrete Math. 7, 167\u2013195 (1974)","journal-title":"Discrete Math."},{"key":"9661_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-642-16926-7_22","volume-title":"Proceedings WG 2010","author":"R. Bevern van","year":"2010","unstructured":"van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring indifference: unit interval vertex deletion. In: Proceedings WG 2010. Lecture Notes in Computer Science, vol.\u00a06410, pp. 232\u2013243. Springer, Berlin (2010)"},{"issue":"5","key":"9661_CR24","doi-asserted-by":"crossref","first-page":"2007","DOI":"10.1137\/070710913","volume":"38","author":"Y.V. Villanger","year":"2009","unstructured":"Villanger, Y.V., Heggernes, P., Paul, C., Telle, J.A.: Interval completion is fixed parameter tractable. SIAM J. Comput. 38(5), 2007\u20132020 (2009)","journal-title":"SIAM J. Comput."},{"key":"9661_CR25","unstructured":"Wegner, G.: Eigenschaften der Nerven homologisch-einfacher Familien im R n . Ph.D. thesis, University of G\u00f6ttingen (1967)"},{"issue":"2","key":"9661_CR26","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9661_CR27","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing 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-012-9661-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9661-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9661-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,29]],"date-time":"2019-06-29T06:34:08Z","timestamp":1561790048000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9661-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,30]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9661"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9661-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,30]]}}}