{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:30:26Z","timestamp":1725456626092},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_21","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T04:42:25Z","timestamp":1350880945000},"page":"194-205","source":"Crossref","is-referenced-by-count":5,"title":["On Group Feedback Vertex Set Parameterized by the Size of the Cutset"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","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. Artif. Intell. Res. (JAIR)\u00a012, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"1","key":"21_CR2","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. Comput. Sci.\u00a05(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set New Measure and New Structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"7","key":"21_CR4","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"issue":"5","key":"21_CR6","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00493-006-0030-1","volume":"26","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Geelen, J., Gerards, B., Goddyn, L.A., Lohman, M., Seymour, P.D.: Packing non-zero a-paths in group-labelled graphs. Combinatorica\u00a026(5), 521\u2013532 (2006)","journal-title":"Combinatorica"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) FOCS, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-28050-4_1","volume-title":"Parameterized and Exact Computation","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On Multiway Cut Parameterized above Lower Bounds. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 1\u201312. Springer, Heidelberg (2012)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-642-22006-7_38","volume-title":"Automata, Languages and Programming","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, part I. LNCS, vol.\u00a06755, pp. 449\u2013461. Springer, Heidelberg (2011)"},{"issue":"3","key":"21_CR10","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F.K.H.A. Dehne","year":"2007","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An \n                    \n                      \n                    \n                    $\\uppercase{O}(2^{\\uppercase{o}(k)}) n^3$\n                   FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst.\u00a041(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"21_CR11","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"21_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S. Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization\u00a08(1), 61\u201371 (2011)","journal-title":"Discrete Optimization"},{"issue":"8","key":"21_CR14","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., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci.\u00a072(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR15","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)"},{"issue":"2","key":"21_CR16","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.jctb.2005.08.001","volume":"96","author":"K.-I. Kawarabayashi","year":"2006","unstructured":"Kawarabayashi, K.-I., Wollan, P.: Non-zero disjoint cycles in highly connected group labelled graphs. J. Comb. Theory, Ser. B\u00a096(2), 296\u2013301 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. CoRR, abs\/1111.2195 (2011)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"3","key":"21_CR18","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR19","unstructured":"Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: LP can be a cure for parameterized problems. In: D\u00fcrr, C., Wilke, T. (eds.) STACS. LIPIcs, vol.\u00a014, pp. 338\u2013349. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"issue":"3","key":"21_CR20","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1159892.1159898","volume":"2","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms\u00a02(3), 403\u2013415 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"8","key":"21_CR21","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci.\u00a075(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"21_CR22","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k\n                  2 kernel for feedback vertex set. ACM Transactions on Algorithms\u00a06(2) (2010)","DOI":"10.1145\/1721837.1721848"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T09:00:43Z","timestamp":1620118843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}