{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:55:14Z","timestamp":1725512114934},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797227"},{"type":"electronic","value":"9783540797234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79723-4_16","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T06:22:17Z","timestamp":1210054937000},"page":"160-171","source":"Crossref","is-referenced-by-count":14,"title":["A Linear Kernel for Planar Feedback Vertex Set"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Eelko","family":"Penninkx","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating sets. J. ACM\u00a051, 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"16_CR2","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 J. Disc. Math.\u00a012, 289\u2013297 (1999)","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR3","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1994, pp. 344\u2013354 (1994)"},{"key":"16_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.: Randomized algorithms for the loop cutset problem. J. Artificial Intelligence Research\u00a012, 219\u2013234 (2000)","journal-title":"J. Artificial Intelligence Research"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A. Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence\u00a083, 167\u2013188 (1996)","journal-title":"Artificial Intelligence"},{"issue":"1","key":"16_CR6","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. Computer Science\u00a05(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Computer Science"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K. Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 192\u2013202. Springer, Heidelberg (2006)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-540-73951-7_37","volume-title":"Algorithms and Data Structures","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for the feedback vertex set problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 422\u2013433. Springer, Heidelberg (2007)"},{"key":"16_CR10","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proceedings STOC 2008 (to appear, 2008)"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"F. Chudak","year":"1998","unstructured":"Chudak, F., Goemans, M., Hochbaum, D., Williamson, D.: A primal\u2013dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letters\u00a022, 111\u2013118 (1998)","journal-title":"Operations Research Letters"},{"key":"16_CR12","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.K.H.A. Dehne","year":"2005","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2\n                  O(k)\n                n\n                3) 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":"16_CR13","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 590\u2013601 (2005)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"16_CR16","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. Congressus Numerantium\u00a087, 161\u2013178 (1992)","journal-title":"Congressus Numerantium"},{"key":"16_CR17","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"16_CR18","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: Handbook of Combinatorial Optimization, Amsterdam, The Netherlands, vol.\u00a0A, pp. 209\u2013258. Kluwer, Dordrecht (1999)"},{"key":"16_CR19","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/11847250_17","volume-title":"Parameterized and Exact Computation","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Gaspers, S., Knauer, C.: Finding a minimum feedback vertex set in time O(1.7548\n                  n\n                ). In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 183\u2013191. Springer, Heidelberg (2006)"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory\u00a051, 53\u201381 (2006)","journal-title":"J. Graph Theory"},{"key":"16_CR22","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 and Company, New York (1979)"},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"M.X. Goemans","year":"1997","unstructured":"Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica\u00a017, 1\u201323 (1997)","journal-title":"Combinatorica"},{"issue":"8","key":"16_CR24","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., Hffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences\u00a072(8), 1386\u20131396 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038, 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"16_CR26","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF02684436","volume":"58","author":"W. Hackbusch","year":"1997","unstructured":"Hackbusch, W.: On the feedback vertex set problem for a planar graph. Computing\u00a058, 129\u2013155 (1997)","journal-title":"Computing"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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\u2013248. Springer, Heidelberg (2004)"},{"key":"16_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"key":"16_CR29","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1995","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1995)"},{"key":"16_CR30","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Universit\u00e4t T\u00fcbingen, Habilitation Thesis (2002)"},{"key":"16_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"16_CR32","doi-asserted-by":"crossref","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster algorithms for feedback vertex set. In: Proceedings 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics, GRACO 2005. Electronic Notes in Discrete Mathematics, vol.\u00a019, pp. 273\u2013279 (2005)","DOI":"10.1016\/j.endm.2005.05.037"},{"key":"16_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11785293_17","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"I. Razgon","year":"2006","unstructured":"Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 160\u2013171. Springer, Heidelberg (2006)"},{"key":"16_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/3-540-53832-1_33","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Stamm","year":"1991","unstructured":"Stamm, H.: On feedback problems in planar digraphs. In: M\u00f6hring, R.H. (ed.) WG 1990. LNCS, vol.\u00a0484, pp. 79\u201389. Springer, Heidelberg (1991)"},{"key":"16_CR35","unstructured":"van Dijk, T.: Fixed parameter complexity of feedback problems. Master\u2019s thesis, Utrecht University (2007)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79723-4_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:30:00Z","timestamp":1619508600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79723-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797227","9783540797234"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79723-4_16","relation":{},"subject":[]}}