{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:45Z","timestamp":1759639065618},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_63","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"750-761","source":"Crossref","is-referenced-by-count":12,"title":["Parameterized Tractability of Multiway Cut with Parity Constraints"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"63_CR1","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is fpt. In: STOC, pp. 459\u2013468 (2011)","DOI":"10.1145\/1993636.1993698"},{"issue":"1","key":"63_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"key":"63_CR3","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"},{"key":"63_CR4","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: SODA, pp. 1713\u20131725 (2012)","DOI":"10.1137\/1.9781611973099.136"},{"key":"63_CR5","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":"63_CR6","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, New York (1999)"},{"key":"63_CR7","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"63_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-58201-0_92","volume-title":"Automata, Languages, and Programming","author":"N. Garg","year":"1994","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway Cuts in Directed and Node Weighted Graphs. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 487\u2013498. Springer, Heidelberg (1994)"},{"issue":"1","key":"63_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jctb.2008.03.006","volume":"99","author":"J. Geelen","year":"2009","unstructured":"Geelen, J., Gerards, B., Reed, B.A., Seymour, P.D., Vetta, A.: On the odd-minor variant of hadwiger\u2019s conjecture. J. Comb. Theory, Ser. B\u00a099(1), 20\u201329 (2009)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"63_CR10","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Li, Z., Reed, B.A.: Recognizing a totally odd k4-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. In: SODA, pp. 318\u2013328 (2010)","DOI":"10.1137\/1.9781611973075.27"},{"key":"63_CR11","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In: SODA, pp. 1183\u20131192 (2009)","DOI":"10.1137\/1.9781611973068.128"},{"key":"63_CR12","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: An (almost) linear time algorithm for odd cyles transversal. In: SODA, pp. 365\u2013378 (2010)","DOI":"10.1137\/1.9781611973075.31"},{"key":"63_CR13","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: Odd cycle packing. In: STOC, pp. 695\u2013704 (2010)","DOI":"10.1145\/1806689.1806785"},{"key":"63_CR14","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A., Wollan, P.: The graph minor algorithm with parity conditions. In: FOCS, pp. 27\u201336 (2011)","DOI":"10.1109\/FOCS.2011.52"},{"key":"63_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: The minimum k-way cut of bounded size is fixed-parameter tractable. In: FOCS, pp. 160\u2013169 (2011)","DOI":"10.1109\/FOCS.2011.53"},{"key":"63_CR16","doi-asserted-by":"crossref","unstructured":"Kakimura, N., Kawarabayashi, K., Kobayashi, Y.: Erd\u00f6s-p\u00f3sa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In: SODA, pp. 1726\u20131736 (2012)","DOI":"10.1137\/1.9781611973099.137"},{"issue":"5","key":"63_CR17","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.jctb.2011.03.004","volume":"101","author":"N. Kakimura","year":"2011","unstructured":"Kakimura, N., Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. J. Comb. Theory, Ser. B\u00a0101(5), 378\u2013381 (2011)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"63_CR18","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF01226465","volume":"31","author":"W Mader","year":"1978","unstructured":"Mader, W.: \u00dcber die Maximalzahl kreuzungsfreier H-Wege. Arch. Math. (Basel)\u00a031(4), 387\u2013402 (1978)","journal-title":"Arch. Math. (Basel)"},{"issue":"3","key":"63_CR19","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. Theoret. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"63_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"63_CR21","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","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, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"63_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume-title":"Algorithms \u2013 ESA 2011","author":"V. Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, Flowers and Vertex Cover. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 382\u2013393. Springer, Heidelberg (2011)"},{"issue":"8","key":"63_CR23","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":"63_CR24","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."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:13Z","timestamp":1620130513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}