{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:18:50Z","timestamp":1742941130449,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319623887"},{"type":"electronic","value":"9783319623894"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62389-4_16","type":"book-chapter","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T15:07:46Z","timestamp":1498835266000},"page":"188-199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A New Kernel for Parameterized Max-Bisection Above Tight Lower Bound"],"prefix":"10.1007","author":[{"given":"Qilong","family":"Feng","sequence":"first","affiliation":[]},{"given":"Senmin","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,1]]},"reference":[{"issue":"1\u20133","key":"16_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.tcs.2007.02.013","volume":"377","author":"J D\u00edaz","year":"2007","unstructured":"D\u00edaz, J., Kami\u0144ski, M.: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theor. Comput. Sci. 377(1\u20133), 271\u2013276 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"16_CR2","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"16_CR3","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00189-7","volume":"79","author":"U Feige","year":"2001","unstructured":"Feige, U., Karpi\u0144ski, M., Langberg, M.: A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. 79(4), 181\u2013188 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for max $$k$$-cut and max bisection. Algorithmica 18(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"issue":"21","key":"16_CR5","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1016\/j.ipl.2010.08.001","volume":"110","author":"G Gutin","year":"2010","unstructured":"Gutin, G., Yeo, A.: Note on maximal bisection above tight lower bound. Inf. Process. Lett. 110(21), 966\u2013969 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/12.67327","volume":"40","author":"DJ Haglin","year":"1991","unstructured":"Haglin, D.J., Venkatesan, S.M.: Approximation and intractability results for the maximum cut problem and its variants. IEEE Trans. Comput. 40(1), 110\u2013113 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1002\/rsa.10035","volume":"20","author":"E Halperin","year":"2002","unstructured":"Halperin, E., Zwick, U.: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Struct. Algorithms 20(3), 382\u2013402 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"16_CR8","first-page":"163","volume":"35","author":"K Jansen","year":"2000","unstructured":"Jansen, K., Karpi\u0144ski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for max-bisection on planar and geometric graph. SIAM J. Comput. 35(1), 163\u2013178 (2000)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"16_CR9","first-page":"369","volume":"7","author":"M Karpi\u0144ski","year":"2000","unstructured":"Karpi\u0144ski, M., Kowaluk, M., Lingas, A.: Approximation algorithms for max bisection on low degree regular graphs and planar graphs. Electron. Colloq. Comput. Complex. 7(7), 369\u2013375 (2000)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"16_CR10","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. NorthHolland, Amsterdam (1986)"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-34611-8_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Mnich","year":"2012","unstructured":"Mnich, M., Zenklusen, R.: Bisections above tight lower bounds. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 184\u2013193. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-34611-8_20"},{"issue":"2","key":"16_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ejor.2010.11.010","volume":"210","author":"B Ries","year":"2011","unstructured":"Ries, B., Zenklusen, R.: A 2-approximation for the maximum satisfying bisection problem. Eur. J. Oper. Res. 210(2), 169\u2013175 (2011)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"16_CR13","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y Ye","year":"2001","unstructured":"Ye, Y.: A 0.699-approximation algorithm for max-bisection. Math. Program. 90(1), 101\u2013111 (2001)","journal-title":"Math. Program."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62389-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:23:50Z","timestamp":1709810630000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62389-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319623887","9783319623894"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62389-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2017.comp.polyu.edu.hk\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}