{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T04:56:43Z","timestamp":1778993803462,"version":"3.51.4"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1401"],"award-info":[{"award-number":["JPMJCR1401"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17H01788"],"award-info":[{"award-number":["JP17H01788"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16K16010"],"award-info":[{"award-number":["JP16K16010"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K19960"],"award-info":[{"award-number":["JP17K19960"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19K21537"],"award-info":[{"award-number":["JP19K21537"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"S\u00e3o Paulo Research Foundation","doi-asserted-by":"crossref","award":["2015\/11937-9"],"award-info":[{"award-number":["2015\/11937-9"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Rio de Janeiro Research Foundation","award":["E-26\/203.272\/2017"],"award-info":[{"award-number":["E-26\/203.272\/2017"]}]},{"DOI":"10.13039\/501100003593","name":"National Council for Scientific and Technological Development","doi-asserted-by":"crossref","award":["308689\/2017-8"],"award-info":[{"award-number":["308689\/2017-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"National Council for Scientific and Technological Development","doi-asserted-by":"crossref","award":["425340\/2016-3"],"award-info":[{"award-number":["425340\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"National Council for Scientific and Technological Development","doi-asserted-by":"crossref","award":["313026\/2017-3"],"award-info":[{"award-number":["313026\/2017-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"National Council for Scientific and Technological Development","doi-asserted-by":"crossref","award":["422829\/2018-8"],"award-info":[{"award-number":["422829\/2018-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"National Council for Scientific and Technological Development","doi-asserted-by":"crossref","award":["303726\/2017-2"],"award-info":[{"award-number":["303726\/2017-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00453-020-00789-1","type":"journal-article","created":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T07:15:59Z","timestamp":1610090159000},"page":"1421-1458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Computing the Largest Bond and the Maximum Connected Cut of a Graph"],"prefix":"10.1007","volume":"83","author":[{"given":"Gabriel L.","family":"Duarte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Eto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6943-856X","authenticated-orcid":false,"given":"Tesshu","family":"Hanaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lehilton L. C.","family":"Pedrosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael C. S.","family":"Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U\u00e9verton S.","family":"Souza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,8]]},"reference":[{"issue":"2","key":"789_CR1","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/j.dam.2008.03.020","volume":"157","author":"REL Aldred","year":"2009","unstructured":"Aldred, R.E.L., Van Dyck, D., Brinkmann, G., Fack, V., McKay, B.D.: Graph structural properties of non-Yutsis graphs allowing fast recognition. Discrete Appl. Math. 157(2), 377\u2013386 (2009)","journal-title":"Discrete Appl. Math."},{"key":"789_CR2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan, C., Brankovic, L., Casel, K., Fernau, H., Jansen, K., Klein, K.M., Lampis, M., Liedloff, M., Monnot, J., Paschos, V.T.: The many facets of upper domination. Theoret. Comput. Sci. 717, 2\u201325 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"789_CR3","volume-title":"The Racah\u2013Wigner Algebra in Quantum Theory","author":"LC Biedenharn","year":"1981","unstructured":"Biedenharn, L.C., Louck, J.D.: The Racah\u2013Wigner Algebra in Quantum Theory. Addison-Wesley, USA (1981)"},{"key":"789_CR4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"1","key":"789_CR5","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."},{"issue":"1","key":"789_CR6","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1006\/inco.1997.2669","volume":"139","author":"HL Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Van Leeuwen, J., Tan, R., Thilikos, D.M.: On interval routing schemes and treewidth. Inf. Comput. 139(1), 92\u2013109 (1997)","journal-title":"Inf. Comput."},{"key":"789_CR7","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.dam.2014.06.001","volume":"196","author":"N Boria","year":"2015","unstructured":"Boria, N., Croce, F.D., Paschos, V.T.: On the max min vertex cover problem. Discrete Appl. Math. 196, 62\u201371 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"789_CR8","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1016\/j.ejc.2012.07.023","volume":"34","author":"BM Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.M., Such\u00fd, O., Telle, J.A., Vatshelle, M.: Feedback vertex set on graphs of low clique-width. Eur. J. Comb. 34(3), 666\u2013679 (2013)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"789_CR9","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1287\/opre.2013.1183","volume":"61","author":"R Carvajal","year":"2013","unstructured":"Carvajal, R., Constantino, M., Goycoolea, M., Vielma, J.P., Weintraub, A.: Imposing connectivity constraints in forest planning models. Oper. Res. 61(4), 824\u2013836 (2013)","journal-title":"Oper. Res."},{"key":"789_CR10","doi-asserted-by":"crossref","unstructured":"Chaourar, B.: A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs. Adv. Oper. Res. 1267108:1\u20131267108:4 (2017)","DOI":"10.1155\/2017\/1267108"},{"key":"789_CR11","unstructured":"Chaourar, B.: Connected max cut is polynomial for graphs without $${K}_5\\setminus e$$ as a minor. CoRR (2019). arXiv:1903.12641"},{"issue":"18","key":"789_CR12","doi-asserted-by":"publisher","first-page":"2456","DOI":"10.1016\/j.dam.2007.06.015","volume":"155","author":"JJ Cho","year":"2007","unstructured":"Cho, J.J., Chen, Y., Ding, Y.: On the (co)girth of a connected matroid. Discrete Appl. Math. 155(18), 2456\u20132470 (2007). https:\/\/doi.org\/10.1016\/j.dam.2007.06.015","journal-title":"Discrete Appl. Math."},{"key":"789_CR13","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"issue":"2","key":"789_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"789_CR15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"789_CR16","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"789_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., Rooij, J.M.M.v., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"789_CR18","unstructured":"de Berg, M., Khosravi, A.: Finding perfect auto-partitions is NP-hard. In: 25th European Workshop on Computational Geometry (EuroCG2009), pp. 255\u2013258 (2009)"},{"issue":"1","key":"789_CR19","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1023\/A:1008765214400","volume":"14","author":"M Demange","year":"1999","unstructured":"Demange, M.: A note on the approximation of a minimum-weight maximal independent set. Comput. Optim. Appl. 14(1), 157\u2013169 (1999)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"789_CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/jgt.21895","volume":"82","author":"G Ding","year":"2016","unstructured":"Ding, G., Dziobiak, S., Wu, H.: Large-or-minors in 3-connected graphs. J. Graph Theory 82(2), 207\u2013217 (2016)","journal-title":"J. Graph Theory"},{"key":"789_CR21","unstructured":"Duarte, G.L., Lokshtanov, D., Pedrosa, L.L.C., Schouery, R.C.S., Souza, U.S.: Computing the Largest Bond of a Graph. In: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Volume148 of LIPIcs, pp. 12:1\u201312:15 (2019)"},{"issue":"11","key":"789_CR22","doi-asserted-by":"crossref","first-page":"1506","DOI":"10.1016\/j.disc.2005.11.088","volume":"307","author":"DV Dyck","year":"2007","unstructured":"Dyck, D.V., Fack, V.: On the reduction of Yutsis graphs. Discrete Math. 307(11), 1506\u20131515 (2007). The Fourth Caracow Conference on Graph Theory","journal-title":"Discrete Math."},{"issue":"1","key":"789_CR23","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 377(1), 271\u2013276 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"789_CR24","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"issue":"2","key":"789_CR25","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02760037","volume":"3","author":"P Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s, P.: On some extremal problems in graph theory. Israel J. Math. 3(2), 113\u2013116 (1965)","journal-title":"Israel J. Math."},{"key":"789_CR26","unstructured":"Eto, H., Hanaka, T., Kobayashi, Y., Kobayashi, Y.: Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Volume148 of LIPIcs, pp. 13:1\u201313:15 (2019)"},{"key":"789_CR27","unstructured":"Flynn, M.: The largest bond in 3-connected graphs. Ph.D. thesis, The University of Mississippi (2017)"},{"issue":"5","key":"789_CR28","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. Comput."},{"key":"789_CR29","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.ipl.2017.06.002","volume":"129","author":"R Gandhi","year":"2018","unstructured":"Gandhi, R., Hajiaghayi, M.T., Kortsarz, G., Purohit, M., Sarpatwar, K.: On maximum leaf trees and connections to connected maximum cut problems. Inf. Processing Lett. 129, 31\u201334 (2018)","journal-title":"Inf. Processing Lett."},{"issue":"2","key":"789_CR30","first-page":"77","volume":"17","author":"R Ganian","year":"2015","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theoret. Comput. Sci. 17(2), 77\u2013100 (2015)","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"789_CR31","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"4","key":"789_CR32","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"789_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory. Graduate Texts in Mathematics","author":"CD Godsil","year":"2001","unstructured":"Godsil, C.D., Royle, G.F.: Algebraic Graph Theory. Graduate Texts in Mathematics. Springer, Berlin (2001)"},{"issue":"6","key":"789_CR34","doi-asserted-by":"crossref","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":"4","key":"789_CR35","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"2","key":"789_CR36","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1080\/10556788.2017.1401069","volume":"34","author":"V Grimm","year":"2019","unstructured":"Grimm, V., Kleinert, T., Liers, F., Schmidt, M., Z\u00f6ttl, G.: Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches. Optim. Methods Softw. 34(2), 406\u2013436 (2019)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"789_CR37","doi-asserted-by":"crossref","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(2), 217\u2013221 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"789_CR38","doi-asserted-by":"crossref","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\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"789_CR39","doi-asserted-by":"crossref","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."},{"key":"789_CR40","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kortsarz, G., MacDavid, R., Purohit, M., Sarpatwar, K.: Approximation algorithms for connected maximum cut and related problems. In: 23rd Annual European Symposium on Algorithms (ESA 2015), Volume 9294 of LNCS, pp. 693\u2013704 (2015)","DOI":"10.1007\/978-3-662-48350-3_58"},{"key":"789_CR41","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Bodlaender, H.L., van der Zanden, T.C., Ono, H.: On the maximum weight minimal separator. In: 14th Annual Conference on Theory and Applications of Models of Computation (TAMC 2017), Volume 10185 of LNCS, pp. 304\u2013318 (2017)","DOI":"10.1007\/978-3-319-55911-7_22"},{"key":"789_CR42","first-page":"85","volume-title":"Reducibility among Combinatorial Problems","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems, pp. 85\u2013103. Springer US, Boston, MA (1972)"},{"key":"789_CR43","doi-asserted-by":"crossref","unstructured":"Khoshkhah, K., Ghadikolaei, M.K., Monnot, J., Sikora, F.: Weighted upper edge cover: Complexity and approximability. In: 13th International Workshop on Algorithms and Computation (WALCOM 2019), Volume 11355 of LNCS, pp. 235\u2013247 (2019)","DOI":"10.1007\/978-3-030-10564-8_19"},{"issue":"1","key":"789_CR44","doi-asserted-by":"crossref","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":"2","key":"789_CR45","doi-asserted-by":"crossref","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"},{"key":"789_CR46","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"issue":"1","key":"789_CR47","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"1063","key":"789_CR48","first-page":"1229","volume":"2","author":"AM Odlyzko","year":"1995","unstructured":"Odlyzko, A.M.: Asymptotic enumeration methods. Handbook Combi. 2(1063), 1229 (1995)","journal-title":"Handbook Combi."},{"issue":"3","key":"789_CR49","first-page":"502","volume":"10","author":"GI Orlova","year":"1972","unstructured":"Orlova, G.I., Dorfman, Y.G.: Finding the maximal cut in a graph. Eng. Cyvernetics 10(3), 502\u2013506 (1972)","journal-title":"Eng. Cyvernetics"},{"key":"789_CR50","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, USA (2006)"},{"issue":"2","key":"789_CR51","doi-asserted-by":"crossref","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":"24","key":"789_CR52","doi-asserted-by":"crossref","first-page":"6157","DOI":"10.1016\/j.disc.2007.11.039","volume":"308","author":"M Rao","year":"2008","unstructured":"Rao, M.: Clique-width of graphs defined by one-vertex extensions. Discrete Math. 308(24), 6157\u20136165 (2008)","journal-title":"Discrete Math."},{"issue":"1","key":"789_CR53","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. excluding a planar graph. J. Comb. Theory, Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"789_CR54","unstructured":"Saurabh, S., Zehavi, M.: Parameterized Complexity of Multi-Node Hubs. In: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Volume115 of LIPIcs, pp. 8:1\u20138:14 (2019)"},{"issue":"1","key":"789_CR55","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10107-017-1154-3","volume":"172","author":"X Shen","year":"2018","unstructured":"Shen, X., Lee, J., Nagarajan, V.: Approximating graph-constrained max-cut. Math. Program. 172(1), 35\u201358 (2018)","journal-title":"Math. Program."},{"key":"789_CR56","doi-asserted-by":"crossref","unstructured":"Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2008), pp. 1\u20138 (2008)","DOI":"10.1109\/CVPR.2008.4587440"},{"issue":"3","key":"789_CR57","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"key":"789_CR58","unstructured":"Yutsis, A.P., Vanagas, V.V., Levinson, I.B.: Mathematical apparatus of the theory of angular momentum. Israel Program for Scientific Translations (1962)"},{"issue":"4","key":"789_CR59","doi-asserted-by":"crossref","first-page":"2440","DOI":"10.1137\/16M109017X","volume":"31","author":"M Zehavi","year":"2017","unstructured":"Zehavi, M.: Maximum minimal vertex cover parameterized by vertex cover. SIAM J. Discrete Math. 31(4), 2440\u20132456 (2017)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00789-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00789-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00789-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T10:22:58Z","timestamp":1617877378000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00789-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,8]]},"references-count":59,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["789"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00789-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,8]]},"assertion":[{"value":"24 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}