{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:52:14Z","timestamp":1725688334307},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_10","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"107-118","source":"Crossref","is-referenced-by-count":9,"title":["Faster Parameterized Algorithms for Deletion to Split Graphs"],"prefix":"10.1007","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","reference":[{"issue":"7","key":"10_CR1","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a076(7), 524\u2013531 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"issue":"4","key":"10_CR3","doi-asserted-by":"publisher","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. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"key":"10_CR4","doi-asserted-by":"publisher","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.\u00a067, 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR5","doi-asserted-by":"publisher","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":"10_CR6","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":"10_CR7","first-page":"311","volume":"19","author":"S. Foldes","year":"1977","unstructured":"Foldes, S., Hammer, P.: Split graphs. Congressus Numerantium\u00a019, 311\u2013315 (1977)","journal-title":"Congressus Numerantium"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. In: SODA, pp. 1737\u20131746 (2012)","DOI":"10.1137\/1.9781611973099.138"},{"key":"10_CR9","doi-asserted-by":"publisher","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.\u00a086, 213\u2013231 (1998)","journal-title":"Discrete Appl. Math."},{"key":"10_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":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/978-3-540-77120-3_79","volume-title":"Algorithms and Computation","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 915\u2013926. Springer, Heidelberg (2007)"},{"issue":"12","key":"10_CR12","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0157(12), 2659\u20132669 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-22953-4_21","volume-title":"Fundamentals of Computation Theory","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.) FCT 2011. LNCS, vol.\u00a06914, pp. 240\u2013251. Springer, Heidelberg (2011)"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","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. Comput. Syst. Sci.\u00a020(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR15","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":"10_CR16","doi-asserted-by":"publisher","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\u00a041, 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","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\u00a057(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"issue":"3-4","key":"10_CR18","doi-asserted-by":"publisher","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\u00a062(3-4), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"10_CR19","unstructured":"Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Lp can be a cure for parameterized problems. In: STACS, pp. 338\u2013349 (2012)"},{"key":"10_CR20","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. Mathematical Notes\u00a048, 1239\u20131245 (1990)","journal-title":"Mathematical Notes"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:24Z","timestamp":1620128904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}