{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:59:13Z","timestamp":1761976753048,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_16","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T07:57:26Z","timestamp":1384847846000},"page":"177-188","source":"Crossref","is-referenced-by-count":2,"title":["A Faster FPT Algorithm for Bipartite Contraction"],"prefix":"10.1007","author":[{"given":"Sylvain","family":"Guillemot","sequence":"first","affiliation":[]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"16_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. CoRR, abs\/1211.5933 (2012), Accepted to SODA 2014","DOI":"10.1137\/1.9781611973402.9"},{"issue":"7","key":"16_CR3","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."},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"key":"16_CR5","doi-asserted-by":"crossref","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\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"issue":"4","key":"16_CR6","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/12086217X","volume":"42","author":"R.H. Chitnis","year":"2013","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM Journal of Computing\u00a042(4), 1674\u20131696 (2013), http:\/\/arxiv.org\/abs\/1110.0259","journal-title":"SIAM Journal of Computing"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-34611-8_21","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: On Group Feedback Vertex Set Parameterized by the Size of the Cutset. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol.\u00a07551, pp. 194\u2013205. Springer, Heidelberg (2012)"},{"issue":"3","key":"16_CR8","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F.K. Dehne","year":"2007","unstructured":"Dehne, F.K., 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. Theor. Comput. Syst.\u00a041(3), 479\u2013492 (2007)","journal-title":"Theor. Comput. Syst."},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-642-32589-2_41","volume-title":"Mathematical Foundations of Computer Science 2012","author":"P.A. Golovach","year":"2012","unstructured":"Golovach, P.A., van \u2019t Hof, P., Paulusma, D.: Obtaining Planarity by Contracting Few Edges. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 455\u2013466. Springer, Heidelberg (2012)"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S. Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversals and cycle-transversals problems. Discrete Optimization\u00a08(1), 61\u201371 (2011)","journal-title":"Discrete Optimization"},{"issue":"8","key":"16_CR11","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., H\u00fcffner, 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":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-28050-4_5","volume-title":"Parameterized and Exact Computation","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)"},{"key":"16_CR13","unstructured":"Heggernes, P., van\u2019t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a Bipartite Graph by Contracting Few Edges. In: FSTTCS 2011, pp. 217\u2013228 (2011)"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K., Yoshida, Y.: Linear-time FPT algorithms via network flow. CoRR, abs\/1307.4927 (2013), Accepted to SODA 2014","DOI":"10.1137\/1.9781611973402.127"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: An (almost) Linear Time Algorithm for Odd Cycle Transversal. In: SODA 2010, pp. 365\u2013378 (2010)","DOI":"10.1137\/1.9781611973075.31"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via Matroids: a Randomized Polynomial Kernel for Odd Cycle Transversal. In: SODA 2012, pp. 94\u2013103 (2012)","DOI":"10.1137\/1.9781611973099.8"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: FOCS 2012, pp. 450\u2013459 (2012)","DOI":"10.1109\/FOCS.2012.46"},{"key":"16_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-642-10217-2_37","volume-title":"Combinatorial Algorithms","author":"D. Lokshtanov","year":"2009","unstructured":"Lokshtanov, D., Saurabh, S., Sikdar, S.: Simpler Parameterized Algorithm for OCT. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol.\u00a05874, pp. 380\u2013384. Springer, Heidelberg (2009)"},{"issue":"3","key":"16_CR19","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theoretical Computer Science\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"16_CR20","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":"16_CR21","doi-asserted-by":"crossref","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms\u00a09(4) (2013)","DOI":"10.1145\/2500119"},{"issue":"3\u20134","key":"16_CR22","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\u20134), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS 1995, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"16_CR24","unstructured":"Narayanaswamy, N., Raman, V., Ramanujan, M., Saurabh, S.: LP can be a cure for Parameterized Problems. In: STACS 2012, pp. 338\u2013349 (2012)"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms via skew-symmetric multicuts. CoRR, abs\/1304.7505 (2013), Accepted to SODA 2014","DOI":"10.1137\/1.9781611973402.126"},{"issue":"4","key":"16_CR26","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"16_CR27","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.1137\/070710913","volume":"38","author":"Y. Villanger","year":"2009","unstructured":"Villanger, Y., Heggernes, P., Paul, C., Telle, J.A.: Interval completion is fixed parameter tractable. SIAM J. Comput.\u00a038(5), 2007\u20132020 (2009)","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-319-03898-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T21:17:04Z","timestamp":1746047824000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}