{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:30Z","timestamp":1725511770815},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_28","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"320-331","source":"Crossref","is-referenced-by-count":21,"title":["A Cubic Kernel for Feedback Vertex Set"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","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":"28_CR2","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":"28_CR3","first-page":"167","volume":"83","author":"A. Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-liker approximation algorithms for the vertex feedback set problem. Acta Informatica\u00a083, 167\u2013188 (1996)","journal-title":"Acta Informatica"},{"issue":"1","key":"28_CR4","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":"28_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1023\/A:1027320705349","volume":"7","author":"H.L. Bodlaender","year":"2003","unstructured":"Bodlaender, H.L.: Necessary edges in k-chordalizations of graphs. Journal of Combinatorial Optimization\u00a07, 283\u2013290 (2003)","journal-title":"Journal of Combinatorial Optimization"},{"key":"28_CR7","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. Technical Report UU-CS-2006-042, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2006)"},{"key":"28_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., et al.: 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":"28_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-44867-5_6","volume-title":"Experimental and Efficient Algorithms","author":"F. Clautiaux","year":"2003","unstructured":"Clautiaux, F., et al.: New lower and upper bounds for graph treewidth. In: Jansen, K., et al. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 70\u201380. Springer, Heidelberg (2003)"},{"key":"28_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.K.H.A. Dehne","year":"2005","unstructured":"Dehne, F.K.H.A., et al.: An o(2O(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":"28_CR11","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":"28_CR12","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume-title":"Handbook of Combinatorial Optimization, vol. A","author":"P. Festa","year":"1999","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of Combinatorial Optimization, vol. A, pp. 209\u2013258. Kluwer Academic Publishers, Amsterdam (1999)"},{"key":"28_CR14","first-page":"135","volume-title":"Handbooks in Operations Research and Management Sciences, vol.7, Network Models","author":"A.M.H. Gerards","year":"1995","unstructured":"Gerards, A.M.H.: Matching. In: Ball, M.O., et al. (eds.) Handbooks in Operations Research and Management Sciences, vol.7, Network Models, pp. 135\u2013224. Elsevier Science, Amsterdam (1995)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/11534273_15","volume-title":"Algorithms and Data Structures","author":"J. Guo","year":"2005","unstructured":"Guo, J., et al.: Improved fixed-parameter algorithms for two feeback set problems. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 158\u2013168. Springer, Heidelberg (2005)"},{"key":"28_CR16","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., Pelmajer, 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":"28_CR17","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"28_CR18","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","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 Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"28_CR19","volume-title":"Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Palo Alto (1988)"},{"key":"28_CR20","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":"28_CR21","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.endm.2005.05.037","volume":"19","author":"V. Raman","year":"2005","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster algorithms for feedback vertex set. Electronic Notes in Discrete Mathematics, Proceedings 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics, GRACO 2005\u00a019, 273\u2013279 (2005)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"28_CR22","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":"28_CR23","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Berlin (2003)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:11:51Z","timestamp":1605744711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_28","relation":{},"subject":[]}}