{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:20:02Z","timestamp":1725852002421},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_51","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"686-699","source":"Crossref","is-referenced-by-count":2,"title":["$$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\\mathcal O}^*(2^p)$$ O \u2217 ( 2 p ) -Time Algorithm and a Polynomial Kernel"],"prefix":"10.1007","author":[{"given":"Saket","family":"Saurabh","sequence":"first","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"Alexander A. Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.: Approximation algorithms for maximum coverage and max cutwith given sizes of parts. In: IPCO, pp. 17\u201330 (1999)"},{"key":"51_CR2","unstructured":"Binkele-Raible, D.: Amortized analysis of exponential time and parameterized algorithms: Measure & conquer and reference search trees. Ph.D. thesis, Universit\n                    \n                      \n                    \n                    $$\\rm \\ddot{a}$$\n                    \n                      \n                        \n                          a\n                          \u00a8\n                        \n                      \n                    \n                  t Trier (2010)"},{"issue":"3","key":"51_CR3","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00453-014-9920-6","volume":"71","author":"E Bonnet","year":"2015","unstructured":"Bonnet, E., Escoffier, B., Paschos, V.T., Tourniaire, E.: Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization. Algorithmica 71(3), 566\u2013580 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"51_CR4","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L.: Parameter complexity of cardinality constrained optimization problems. Comput. J. 51(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"51_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/11847250_22","volume-title":"Parameterized and Exact Computation","author":"L Cai","year":"2006","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 239\u2013250. Springer, Heidelberg (2006)"},{"key":"51_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2013.10.026","volume":"513","author":"R Crowston","year":"2013","unstructured":"Crowston, R., Gutin, G., Jones, M., Muciaccia, G.: Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci. 513, 53\u201364 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"51_CR7","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1007\/s00453-014-9870-z","volume":"72","author":"R Crowston","year":"2015","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-cut parameterized above the Edwards-Erd\u0151s bound. Algorithmica 72(3), 734\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"51_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)"},{"key":"51_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"issue":"2","key":"51_CR10","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"6","key":"51_CR11","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"51_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SICOMP 37(1), 319\u2013357 (2007)","journal-title":"SICOMP"},{"issue":"2","key":"51_CR13","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 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"51_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"51_CR15","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2007.05.014","volume":"104","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S.: Improved fixed parameter tractable algorithms for two \u201cedge\u201d problems: MAXCUT and MAXDAG. Inf. Process. Lett. 104(2), 65\u201372 (2007)","journal-title":"Inf. Process. Lett."},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Zehavi, M.: Parameterized algorithms for graph partitioning problems. In: WG, pp. 384\u2013395 (2014)","DOI":"10.1007\/978-3-319-12340-0_32"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T20:35:06Z","timestamp":1559421306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}