{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:12:39Z","timestamp":1742947959460,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642280498"},{"type":"electronic","value":"9783642280504"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28050-4_5","type":"book-chapter","created":{"date-parts":[[2012,3,9]],"date-time":"2012-03-09T04:40:26Z","timestamp":1331268026000},"page":"55-66","source":"Crossref","is-referenced-by-count":6,"title":["Contracting Graphs to Paths and Trees"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"L\u00e9v\u00eaque","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","first-page":"844","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J.\u00a0ACM\u00a042, 844\u2013856 (1995)","journal-title":"J.\u00a0ACM"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(83)90012-0","volume":"26","author":"T. Asano","year":"1983","unstructured":"Asano, T., Hirata, T.: Edge-contraction problems. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a026, 197\u2013208 (1983)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/978-3-642-16926-7_22","volume-title":"Graph Theoretic Concepts in Computer Science","author":"R. Bevern van","year":"2010","unstructured":"van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring Indifference: Unit Interval Vertex Deletion. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 232\u2013243. Springer, Heidelberg (2010)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-17493-3_6","volume-title":"Parameterized and Exact Computation","author":"D. Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: Enumerate & Measure: Improving Parameter Budget Management. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 38\u201349. Springer, Heidelberg (2010)"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci.\u00a05, 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proc.\u00a0FOCS, pp. 629\u2013638. IEEE (2009)","key":"5_CR6","DOI":"10.1109\/FOCS.2009.46"},{"issue":"8","key":"5_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"35","key":"5_CR8","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci.\u00a0412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"A.E. Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. Journal of Graph Theory\u00a011(1), 71\u201379 (1987)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"5_CR10","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. Inf. Process. Lett.\u00a058(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set New Measure and New Structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"7","key":"5_CR12","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proc.\u00a0FOCS 2011 (to appear, 2011)","key":"5_CR14"},{"issue":"3","key":"5_CR15","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F.K.H.A. Dehne","year":"2007","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst.\u00a041(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"5_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"5_CR17","series-title":"Monographs in Computer Science","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. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"issue":"8","key":"5_CR18","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., Huffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci.\u00a072(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR19","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., 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)"},{"key":"5_CR20","series-title":"LNCS","first-page":"55","volume-title":"IPEC 2011","author":"P. Heggernes","year":"2012","unstructured":"Heggernes, P., van \u2019t Hof, P., L\u00e9v\u00eaque, B., Lokshtanov, D., Paul, C.: Contracting graphs to paths and trees. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 55\u201366. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: An (almost) linear time algorithm for odd cycles transversal. In: Proc.\u00a0SODA 2010, pp. 365\u2013378. ACM-SIAM (2010)","key":"5_CR21","DOI":"10.1137\/1.9781611973075.31"},{"issue":"4","key":"5_CR22","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"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/978-3-540-74839-7_28","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Marx","year":"2007","unstructured":"Marx, D., Schlotter, I.: Obtaining a Planar Graph by Vertex Deletion. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 292\u2013303. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proc.\u00a0FOCS 1995, pp. 182\u2013191. IEEE (1995)","key":"5_CR24","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"1","key":"5_CR25","doi-asserted-by":"publisher","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. Disc. Appl. Math.\u00a0113(1), 109\u2013128 (2001)","journal-title":"Disc. Appl. Math."},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-16926-7_19","volume-title":"Graph Theoretic Concepts in Computer Science","author":"G. Philip","year":"2010","unstructured":"Philip, G., Raman, V., Villanger, Y.: A Quartic Kernel for Pathwidth-One Vertex Deletion. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 196\u2013207. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k 2 vertex kernel for feedback vertex set. ACM Transactions on Algorithms\u00a06(2) (2010)","key":"5_CR27","DOI":"10.1145\/1721837.1721848"},{"key":"5_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-17493-3_22","volume-title":"Parameterized and Exact Computation","author":"Y. Villanger","year":"2010","unstructured":"Villanger, Y.: Proper Interval Vertex Deletion. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 228\u2013238. Springer, Heidelberg (2010)"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(81)90039-1","volume":"3","author":"T. Watanabe","year":"1981","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the removal of forbidden graphs by edge-deletion or edge-contraction. Disc. Appl. Math.\u00a03, 151\u2013153 (1981)","journal-title":"Disc. Appl. Math."},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(83)90101-4","volume":"6","author":"T. Watanabe","year":"1983","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the NP-hardness of edge-deletion and edge-contraction problems. Disc. Appl. Math.\u00a06, 63\u201378 (1983)","journal-title":"Disc. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node and edge-deletion NP-complete problems. In: Proc.\u00a0STOC 1978, pp. 253\u2013264. ACM (1978)","key":"5_CR31","DOI":"10.1145\/800133.804355"},{"issue":"4","key":"5_CR32","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1145\/322154.322157","volume":"26","author":"M. Yannakakis","year":"1979","unstructured":"Yannakakis, M.: The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM\u00a026(4), 618\u2013630 (1979)","journal-title":"J. ACM"},{"issue":"2","key":"5_CR33","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput.\u00a010(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28050-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T20:14:47Z","timestamp":1742674487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28050-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280498","9783642280504"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28050-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}