{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:44Z","timestamp":1759639004233,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250041"},{"type":"electronic","value":"9783030250058"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-25005-8_27","type":"book-chapter","created":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T23:02:23Z","timestamp":1563145343000},"page":"327-338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number"],"prefix":"10.1007","author":[{"given":"Yasuaki","family":"Kobayashi","sequence":"first","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"issue":"1","key":"27_CR1","first-page":"14","volume":"7","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of the maximum cut problem. Nordic J. Comput. 7(1), 14\u201331 (2000)","journal-title":"Nordic J. Comput."},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Chimani, M., Dahn, C., Juhnke-Kubitzke, M., Kriegem, N.M., Mutzel, P., Nover, A.: Maximum Cut Parameterized by Crossing Number. arXiv:1903.06061 (2019)","DOI":"10.7155\/jgaa.00523"},{"issue":"3","key":"27_CR3","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\u00f6s Bound. Algorithmica 72(3), 734\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-319-94667-2_12","volume-title":"Combinatorial Algorithms","author":"C Dahn","year":"2018","unstructured":"Dahn, C., Kriege, N.M., Mutzel, P.: A fixed-parameter algorithm for the max-cut problem on embedded 1-planar graphs. In: Iliopoulos, C., Leong, H.W., Sung, W.-K. (eds.) IWOCA 2018. LNCS, vol. 10979, pp. 141\u2013152. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94667-2_12"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of STOC 1983, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"issue":"2","key":"27_CR6","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/PL00011425","volume":"90","author":"A Galluccio","year":"2001","unstructured":"Galluccio, A., Loebl, M., Vondr\u00e1k, J.: Optimization via enumeration: a new algorithm for the max cut problem. Math. Program. 90(2), 273\u2013290 (2001)","journal-title":"Math. Program."},{"issue":"4","key":"27_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3111499","volume":"13","author":"Serge Gaspers","year":"2017","unstructured":"Gaspers, S., Sorkin, G.B.: Separate, measure and conquer: faster polynomial-space algorithms for max 2-CSP and counting dominating sets. ACM Trans. Algorithms 13(4), 44:1\u201344:36 (2017)","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"27_CR8","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 problem using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(99)00056-6","volume":"92","author":"V Guruswami","year":"1999","unstructured":"Guruswami, V.: Maximum cut on line and total graphs. Discrete Appl. Math. 92, 217\u2013221 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013255 (1975)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"27_CR11","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"27_CR13","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? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"27_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s10589-010-9335-5","volume":"51","author":"F Liers","year":"2012","unstructured":"Liers, F., Pardella, G.: Partitioning planar graphs: a fast combinatorial approach for max-cut. Comput. Optim. Appl. 51(1), 323\u2013344 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"27_CR15","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-319-90530-3_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"J Madathil","year":"2018","unstructured":"Madathil, J., Saurabh, S., Zehavi, M.: Max-Cut Above Spanning Tree is fixed-parameter tractable. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 244\u2013256. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90530-3_21"},{"issue":"2","key":"27_CR17","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":"27_CR18","first-page":"502","volume":"10","author":"GI Orlova","year":"1972","unstructured":"Orlova, G.I.: Dorfman: finding the maximal cut in a graph. Eng. Cybern. 10(3), 502\u2013506 (1972)","journal-title":"Eng. Cybern."},{"key":"27_CR19","unstructured":"Pilipczuk, M., Pilipczuk, M., Wrochna, M.: Edge bipartization faster then $$2^k$$. In: Proceedings of IPEC 2016. LIPIcs. vol. 62, pp. 26:1\u201326:13 (2016)"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.endm.2016.10.040","volume":"55","author":"RV Pocai","year":"2016","unstructured":"Pocai, R.V.: The complexity of SIMPLE MAX-CUT on comparability graphs. Electron. Notes Discrete Math. 55, 161\u2013164 (2016)","journal-title":"Electron. Notes Discrete Math."},{"issue":"2","key":"27_CR21","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."},{"issue":"5","key":"27_CR22","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1109\/12.53581","volume":"39","author":"W-K Shih","year":"1990","unstructured":"Shih, W.-K., Wu, S., Kuo, Y.S.: Unifying maximum cut and minimum cut of a planar graph. IEEE Trans. Comput. 39(5), 694\u2013697 (1990)","journal-title":"IEEE Trans. Comput."},{"issue":"6","key":"27_CR23","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"27_CR24","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proceedings of STOC 1978, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-25005-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:15:09Z","timestamp":1710350109000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25005-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250041","9783030250058"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25005-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2019.di.unipi.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5-6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}