{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:11:20Z","timestamp":1725567080438},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_87","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"859-869","source":"Crossref","is-referenced-by-count":30,"title":["An O(2 O(k) n 3) FPT Algorithm for\u00a0the\u00a0Undirected\u00a0Feedback\u00a0Vertex\u00a0Set\u00a0Problem"],"prefix":"10.1007","author":[{"given":"Frank","family":"Dehne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim","family":"Stevens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"87_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"87_CR2","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),, New Orleans, January 2004. Proc. Applied Mathematics, vol.\u00a0115, ACM\/SIAM (2004)"},{"key":"87_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":"87_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":"87_CR5","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R. Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM Journal on Computing\u00a027, 942\u2013959 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"87_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":"87_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-28639-4_10","volume-title":"Parameterized and Exact Computation","author":"Y. Chen","year":"2004","unstructured":"Chen, Y., Flum, J.: On miniaturized problems in parameterized complexity theory. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 108\u2013120. Springer, Heidelberg (2004)"},{"key":"87_CR8","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. Journal of Computer and System Sciences\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"87_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-540-31856-9_22","volume-title":"STACS 2005","author":"J. Chen","year":"2005","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 269\u2013280. Springer, Heidelberg (2005)"},{"key":"87_CR10","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"R. Downey","year":"2003","unstructured":"Downey, R., Estivill-Castro, V., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Cutting up is hard to do: the complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science\u00a078, 205\u2013218 (2003)","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"87_CR11","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":"87_CR12","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, Heidelberg (1999)"},{"key":"87_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-540-39890-5_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Dehne","year":"2003","unstructured":"Dehne, F., Fellows, M., Rosamond, F.: An FPT algorithm for set splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 180\u2013191. Springer, Heidelberg (2003)"},{"key":"87_CR14","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":"87_CR15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J., Scheiber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica\u00a020, 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"87_CR16","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1021\/ci030411+","volume":"44","author":"C. Fried","year":"2004","unstructured":"Fried, C., Hordijk, W., Prohaska, S.J., Stadler, C.R., Stadler, P.F.: The footprint sorting problem. J. Chem. Inf. Comput. Sci.\u00a044, 332\u2013338 (2004)","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"87_CR17","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","volume":"49","author":"M. Fellows","year":"2003","unstructured":"Fellows, M., Hallett, M., Stege, U.: Analogs and duals of the MAST problem for sequences and trees. Journal of Algorithms\u00a049, 192\u2013216 (2003)","journal-title":"Journal of Algorithms"},{"key":"87_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","author":"J. Guo","year":"2005","unstructured":"Guo, J., Gramm, J., Hueffner, 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, Springer, Heidelberg (2005) (to appear)"},{"key":"87_CR19","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":"87_CR20","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. Kanj","year":"2004","unstructured":"Kanj, I., Pelsmajer, M., 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":"87_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF00137392","volume":"1","author":"A. Kunzmann","year":"1990","unstructured":"Kunzmann, A., Wunderlich, H.: An analytical approach to the partial scan problem. Journal of Electronic Testing: Theory and Applications\u00a01, 163\u2013174 (1990)","journal-title":"Journal of Electronic Testing: Theory and Applications"},{"key":"87_CR22","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Manuscript (2004)"},{"key":"#cr-split#-87_CR23.1","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms, Habilitationschrift, University of Tubingen (2002);"},{"key":"#cr-split#-87_CR23.2","unstructured":"Electronic file available from R. Niedermeier"},{"key":"87_CR24","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (forthcoming)"},{"key":"87_CR25","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.: 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":"87_CR26","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. Elsevier, April 27-29. Electronic Notes in Discrete Mathematics (2005) (to appear)"},{"key":"87_CR27","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032, 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"87_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_87","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T07:21:22Z","timestamp":1553152882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11533719_87","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}