{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:12:15Z","timestamp":1743117135240,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642280498"},{"type":"electronic","value":"9783642280504"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28050-4_1","type":"book-chapter","created":{"date-parts":[[2012,3,8]],"date-time":"2012-03-08T23:40:26Z","timestamp":1331250026000},"page":"1-12","source":"Crossref","is-referenced-by-count":18,"title":["On Multiway Cut Parameterized above Lower Bounds"],"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"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Proc. of STOC 2011 (to appear, 2011)","key":"1_CR1"},{"issue":"1","key":"1_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"},{"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. In: Proc. of STOC 2008, pp. 177\u2013186 (2008)","key":"1_CR3","DOI":"10.1145\/1374376.1374404"},{"issue":"4","key":"1_CR4","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput.\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"1_CR5","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), \n                  \n                    citeseer.ist.psu.edu\/downey98parameterized.html"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR7","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, 1st edn. An EATCS Series. Springer, Heidelberg (2006), \n                  \n                    http:\/\/www.worldcat.org\/isbn\/3540299521","edition":"1"},{"issue":"1","key":"1_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N. Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms\u00a050(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-79723-4_13","volume-title":"Parameterized and Exact Computation","author":"S. Guillemot","year":"2008","unstructured":"Guillemot, S.: FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 129\u2013140. Springer, Heidelberg (2008)"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-642-15775-2_28","volume-title":"Algorithms \u2013 ESA 2010","author":"G. Gutin","year":"2010","unstructured":"Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average have Kernels with Quadratic Numbers of Variables. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I, LNCS, vol.\u00a06346, pp. 326\u2013337. Springer, Heidelberg (2010)"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst.\u00a048(2), 402\u2013410 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: Maxsat and maxcut. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"1_CR13","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."},{"unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proc. of STOC 2011 (to appear, 2011)","key":"1_CR14"},{"key":"1_CR15","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. Oxford University Press, USA (2006), \n                  \n                    http:\/\/www.worldcat.org\/isbn\/0198566077"},{"key":"1_CR16","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)"},{"unstructured":"Razgon, I.: Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs\/1011.6267 (2010)","key":"1_CR17"},{"unstructured":"Razgon, I.: Large isolating cuts shrink the multiway cut. CoRR abs\/1104.5361 (2011)","key":"1_CR18"},{"issue":"8","key":"1_CR19","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":"1_CR20","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00224-009-9215-5","volume":"46","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst.\u00a046(4), 723\u2013736 (2010)","journal-title":"Theory Comput. Syst."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28050-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T09:34:26Z","timestamp":1556444066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28050-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280498","9783642280504"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28050-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}