{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T02:52:58Z","timestamp":1770432778626,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540390985","type":"print"},{"value":"9783540391012","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11847250_18","type":"book-chapter","created":{"date-parts":[[2006,9,13]],"date-time":"2006-09-13T15:43:02Z","timestamp":1158162182000},"page":"192-202","source":"Crossref","is-referenced-by-count":28,"title":["The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Burrage","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Estivill-Castro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shev","family":"Mac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: theory and experiments. In: Arge, L., Italiano, G., Sedgewick, R. (eds.) Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX) Proc. Applied Mathematics 115, New Orleans, January 2004. ACM\/SIAM (2004)"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Polynomial time data reduction for dominating set. Journal of the ACM\u00a051, 363\u2013384 (2004)","journal-title":"Journal of the ACM"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics\u00a012, 289\u2013297 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Random algorithms for the loop cutset problem. Journal of Artificial Intelligence Research\u00a012, 219\u2013234 (2000)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"H. Bodlaender","year":"2005","unstructured":"Bodlaender, H., Koster, A., van den Eijkhof, F.: Preprocessing rules for triangulation of probabilistic networks. Computational Intelligence\u00a021, 286\u2013305 (2005)","journal-title":"Computational Intelligence"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H. Bodlaender","year":"1994","unstructured":"Bodlaender, H.: On disjoint cycles. International Journal of Foundations of Computer Science\u00a05, 59\u201368 (1994)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in O(n\n                        2) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"key":"18_CR8","first-page":"161","volume":"87","author":"R. Downey","year":"1992","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. Congressus Numerantium\u00a087, 161\u2013187 (1992)","journal-title":"Congressus Numerantium"},{"key":"18_CR9","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, Heidelberg (1999)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/11533719_87","volume-title":"Computing and Combinatorics","author":"F. Dehne","year":"2005","unstructured":"Dehne, F., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O\n                        *(2\n                           O(k)) FPT algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 859\u2013869. Springer, Heidelberg (2005)"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F. Dehne","year":"2004","unstructured":"Dehne, F., Fellows, M., Rosamond, F.A., Shaw, P.: Greedy localization, iterative compression and modeled crown reductions: new FPT techniques, an improved algorithm for set splitting and a novel 2k kernelization for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 271\u2013280. Springer, Heidelberg (2004)"},{"key":"18_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/978-3-540-27836-8_48","volume-title":"Automata, Languages and Programming","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2\n                        n nondeterministic bits. In: D\u00edaz, J., et al. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 555\u2013567. Springer, Heidelberg (2004)"},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume-title":"Handbook of Combinatorial Optimization","author":"P. Festa","year":"1999","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol.\u00a0A, pp. 209\u2013258. Kluwer, Dordrecht (1999)"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/11534273_15","volume-title":"Algorithms and Data Structures","author":"J. Guo","year":"2005","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Improved fixed-parameter algorithms for two feedback set problems. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 158\u2013169. Springer, Heidelberg (2005)"},{"key":"18_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"18_CR17","unstructured":"Guo, J.: Algorithm design techniques for parameterized problems. Ph.D. Thesis, Friedrich-Schiller-Universit\u00e4t, Jena (2006)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-28639-4_21","volume-title":"Parameterized and Exact Computation","author":"I.A. Kanj","year":"2004","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 235\u2013247. Springer, Heidelberg (2004)"},{"key":"18_CR19","unstructured":"Lokshtanov, D., Sloper, C.: Fixed-parameter set-splitting, linear kernel and improved running time. In: Algorithms and Complexity in Durham 2005: Proceedings of the First ACiD Workshop. Texts in Algorithmics, vol.\u00a04, pp. 105\u2013113. King\u2019s College Press (2005)"},{"key":"18_CR20","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms, Habilitationschrift, University of Tubingen (2002) (Electronic file available from R. Niedermeier)"},{"key":"18_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"18_CR23","unstructured":"Prieto-Rodriguez, E.: Systematic kernelization in FPT algorithm design. Ph.D. Thesis, School of EE&CS, University of Newcastle, Australia (2005)"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/3-540-36136-7_22","volume-title":"Algorithms and Computation","author":"V. Raman","year":"2002","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 241\u2013248. Springer, Heidelberg (2002)"},{"key":"18_CR25","series-title":"Electronic Notes in Discrete Mathematics","volume-title":"Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2005","author":"V. Raman","year":"2005","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster algorithms for feedback vertex set. In: Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2005, Angra dos Reis (Rio de Janeiro), Brazil, April 27-29, 2005. Electronic Notes in Discrete Mathematics. Elsevier, Amsterdam (2005)"},{"key":"18_CR26","unstructured":"Sloper, C.: Techniques in parameterized algorithm design. Ph.D. Thesis, Department of Informatics, University of Bergen, Norway (2005)"},{"key":"18_CR27","unstructured":"Weihe, K.: Covering trains by stations, or the power of data reduction. In: Proc. ALEX 1998, pp. 1\u20138 (1998)"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44691-5_1","volume-title":"Algorithm Engineering","author":"K. Weihe","year":"2001","unstructured":"Weihe, K.: On the Differences Between \u2018Practical\u2019 and \u2018Applied\u2019 (invited paper). In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol.\u00a01982, pp. 1\u201310. Springer, Heidelberg (2001)"},{"key":"18_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-540-28639-4_5","volume-title":"Parameterized and Exact Computation","author":"M. Weyer","year":"2004","unstructured":"Weyer, M.: Bounded fixed-parameter tractability: the case of 2\n                           poly(k). In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 49\u201360. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11847250_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:18:41Z","timestamp":1619507921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11847250_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540390985","9783540391012"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11847250_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}