{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:21:25Z","timestamp":1725549685732},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281016"},{"type":"electronic","value":"9783540317111"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_15","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:31:47Z","timestamp":1268400707000},"page":"158-168","source":"Crossref","is-referenced-by-count":13,"title":["Improved Fixed-Parameter Algorithms for Two Feedback Set Problems"],"prefix":"10.1007","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Gramm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Falk","family":"H\u00fcffner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Wernicke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"3","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\u00a03(2), 289\u2013297 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"15_CR2","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.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM Journal on Computing\u00a027(4), 942\u2013959 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR3","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. Journal of Artificial Intelligence Research\u00a012, 219\u2013234 (2000)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"15_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. International Journal of Foundations of Computer Science\u00a05, 59\u201368 (1994)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"15_CR5","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., Langston, M., Rosamond, F., Stevens, K.: An $\\mathcal O^*(2^{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":"15_CR6","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\u2013187 (1992)","journal-title":"Congressus Numerantium"},{"key":"15_CR7","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":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-540-45078-8_44","volume-title":"Algorithms and Data Structures","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 505\u2013520. Springer, Heidelberg (2003)"},{"key":"15_CR9","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":"15_CR10","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Hardy, N., Reed, B., Vetta, A.: Planar graph bipartization in linear time. In: Proc. 2nd GRACO. Electronic Notes in Discrete Mathematics (2005)","DOI":"10.1016\/j.endm.2005.05.036"},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing\u00a025(2), 235\u2013251 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/11427186_22","volume-title":"Experimental and Efficient Algorithms","author":"F. H\u00fcffner","year":"2005","unstructured":"H\u00fcffner, F.: Algorithm engineering for optimal graph bipartization. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 240\u2013252. Springer, Heidelberg (2005)"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Kahng, A.B., Vaya, S., Zelikovsky, A.: New graph bipartizations for double-exposure, bright field alternating phase-shift mask layout. In: Proc. Asia and South Pacific Design Automation Conference, pp. 133\u2013138 (2001)","DOI":"10.1145\/370155.370304"},{"key":"15_CR14","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":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-56939-1_60","volume-title":"Automata, Languages and Programming","author":"C. Lund","year":"1993","unstructured":"Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 40\u201351. Springer, Heidelberg (1993)"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-28629-5_4","volume-title":"Mathematical Foundations of Computer Science 2004","author":"R. Niedermeier","year":"2004","unstructured":"Niedermeier, R.: Ubiquitous parameterization\u2014invitation to fixed-parameter algorithms. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 84\u2013103. Springer, Heidelberg (2004)"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2005) (forthcoming)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1101\/gr.1536204","volume":"14","author":"M. Pop","year":"2004","unstructured":"Pop, M., Kosack, D.S., Salzberg, S.L.: Hierarchical scaffolding with Bambus. Genome Research\u00a014, 149\u2013159 (2004)","journal-title":"Genome Research"},{"key":"15_CR20","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":"15_CR21","doi-asserted-by":"crossref","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster algorithms for feedback vertex set. In: Proc. 2nd GRACO. Electronic Notes in Discrete Mathematics (2005)","DOI":"10.1016\/j.endm.2005.05.037"},{"key":"15_CR22","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":"15_CR23","unstructured":"Wernicke, S.: On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Diplomarbeit, WSI f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:09:52Z","timestamp":1605643792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11534273_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}