{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T16:00:20Z","timestamp":1777996820722,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,10,5]],"date-time":"2013-10-05T00:00:00Z","timestamp":1380931200000},"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":[[2015,4]]},"DOI":"10.1007\/s00453-013-9837-5","type":"journal-article","created":{"date-parts":[[2013,10,4]],"date-time":"2013-10-04T15:58:01Z","timestamp":1380902281000},"page":"989-1006","source":"Crossref","is-referenced-by-count":26,"title":["Faster Parameterized Algorithms for Deletion to Split Graphs"],"prefix":"10.1007","volume":"71","author":[{"given":"Esha","family":"Ghosh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,5]]},"reference":[{"issue":"7","key":"9837_CR1","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"F. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9837_CR2","series-title":"Proceedings, Part I. Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming, 36th International Colloquium, ICALP 2009","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, 5\u201312 July 2009, Proceedings, Part I. Lecture Notes in Computer Science, vol. 5555, pp. 49\u201358. Springer, Berlin (2009)"},{"issue":"4","key":"9837_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":"9837_CR4","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67, 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5\u20136","key":"9837_CR5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.ipl.2013.01.001","volume":"113","author":"M. Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M.: Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5\u20136), 179\u2013182 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"9837_CR6","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"9837_CR7","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, Berlin (1999)"},{"key":"9837_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","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":"9837_CR9","first-page":"311","volume":"19","author":"S. F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.: Split graphs. Congr. Numer. 19, 311\u2013315 (1977)","journal-title":"Congr. Numer."},{"key":"9837_CR10","series-title":"LIPIcs","first-page":"32","volume-title":"30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013","author":"F.V. Fomin","year":"2013","unstructured":"Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, 27 February\u20132 March 2013, Kiel, Germany, LIPIcs, vol. 20, pp. 32\u201343. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Wadern (2013)"},{"key":"9837_CR11","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1137\/1.9781611973099.138","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012","author":"F.V. Fomin","year":"2012","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17\u201319 January 2012, pp. 1737\u20131746. SIAM, Philadelphia (2012)"},{"key":"9837_CR12","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","volume":"86","author":"T. Fujito","year":"1998","unstructured":"Fujito, T.: A unified approximation algorithm for node-deletion problems. Discrete Appl. Math. 86, 213\u2013231 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9837_CR13","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":"9837_CR14","first-page":"915","volume-title":"Proceedings of the 18th International Conference on Algorithms and Computation, ISAAC\u201907","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Proceedings of the 18th International Conference on Algorithms and Computation, ISAAC\u201907, pp. 915\u2013926. Springer, Berlin, Heidelberg (2007)"},{"issue":"3","key":"9837_CR15","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"P.L. Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1(3), 275\u2013284 (1981)","journal-title":"Combinatorica"},{"issue":"12","key":"9837_CR16","doi-asserted-by":"crossref","first-page":"2659","DOI":"10.1016\/j.dam.2008.08.010","volume":"157","author":"P. Heggernes","year":"2009","unstructured":"Heggernes, P., Mancini, F.: Minimal split completions. Discrete Appl. Math. 157(12), 2659\u20132669 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9837_CR17","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 of the Fundamentals of Computation Theory\u201418th International Symposium, FCT 2011","author":"P. Heggernes","year":"2011","unstructured":"Heggernes, P., van \u2019t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.: Parameterized complexity of vertex deletion into perfect graph classes. In: Owe, O., Steffen, M., Telle, J.A. (eds.) Proceedings of the Fundamentals of Computation Theory\u201418th International Symposium, FCT 2011, Oslo, Norway, 22\u201325 August 2011. Lecture Notes in Computer Science, vol. 6914, pp. 240\u2013251. Springer, Berlin (2011)."},{"issue":"2","key":"9837_CR18","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":"9837_CR19","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. CoRR abs\/1203.0833 (2012)"},{"key":"9837_CR20","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"4","key":"9837_CR21","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":"9837_CR22","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"},{"issue":"1","key":"9837_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."},{"key":"9837_CR24","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1007\/BF01240267","volume":"48","author":"R.I. Tyshkevich","year":"1990","unstructured":"Tyshkevich, R.I., Chernyak, A.A.: Yet another method of enumerating unmarked combinatorial objects. Math. Notes - Ross. Akad. 48, 1239\u20131245 (1990)","journal-title":"Math. Notes - Ross. Akad."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9837-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9837-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9837-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9837-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,5]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9837"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9837-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,5]]}}}