{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T15:10:26Z","timestamp":1745334626454},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:00:00Z","timestamp":1683244800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:00:00Z","timestamp":1683244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00453-023-01128-w","type":"journal-article","created":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T04:04:13Z","timestamp":1683259453000},"page":"3024-3057","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Philip N.","family":"Klein","sequence":"first","affiliation":[]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,5]]},"reference":[{"issue":"5","key":"1128_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 1\u201327 (2008)","journal-title":"J. ACM"},{"key":"1128_CR2","doi-asserted-by":"crossref","unstructured":"Alpert, S., Galun, M., Basri, R., Brandt, A.: Image segmentation by probabilistic bottom-up aggregation and cue integration. In: Computer Vision and Pattern Recognition, pp. 1\u20138. IEEE (2007)","DOI":"10.1109\/CVPR.2007.383017"},{"issue":"10","key":"1128_CR3","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1109\/TPAMI.2011.280","volume":"34","author":"A Alush","year":"2012","unstructured":"Alush, A., Goldberger, J.: Ensemble segmentation using efficient integer linear programming. Pattern Anal. Mach. Intell. 34(10), 1966\u20131977 (2012)","journal-title":"Pattern Anal. Mach. Intell."},{"key":"1128_CR4","doi-asserted-by":"crossref","unstructured":"Alush, A., Goldberger, J.: Break and conquer: Efficient correlation clustering for image segmentation. In: Similarity-Based Pattern Recognition, vol. 7953, pp. 134\u2013147. Springer (2013)","DOI":"10.1007\/978-3-642-39140-8_9"},{"key":"1128_CR5","doi-asserted-by":"crossref","unstructured":"Andres, B., Kappes, J.H., Beier, T., Kothe, U., Hamprecht, F.A.: Probabilistic image segmentation with closedness constraints. In: International Conference on Computer Vision, pp. 2611\u20132618. IEEE (2011)","DOI":"10.1109\/ICCV.2011.6126550"},{"key":"1128_CR6","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Kohli, P., Kolmogorov, V., Zadimoghaddam, M.: Optimal coalition structure generation in cooperative graph games. In: Conference on Artificial Intelligence (2013)","DOI":"10.1609\/aaai.v27i1.8653"},{"issue":"1\u20133","key":"1128_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1\u20133), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"key":"1128_CR8","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for planar multiway cut. In: Symposium on Discrete Algorithms, pp. 639\u2013655. SIAM (2012)","DOI":"10.1137\/1.9781611973099.54"},{"issue":"5","key":"1128_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/2027216.2027219","volume":"58","author":"M Bateni","year":"2011","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21 (2011)","journal-title":"J. ACM"},{"issue":"3\/4","key":"1128_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/106652799318274","volume":"6","author":"A Ben-Dor","year":"1999","unstructured":"Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3\/4), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"1128_CR11","doi-asserted-by":"crossref","unstructured":"Berger, A., Grigni, M.: Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In: International Colloquium on Automata, Languages and Programming, vol. 4596, pp. 90\u2013101 (2007)","DOI":"10.1007\/978-3-540-73420-8_10"},{"issue":"2","key":"1128_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-012-9662-2","volume":"68","author":"G Borradaile","year":"2014","unstructured":"Borradaile, G., Demaine, E.D., Tazari, S.: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica 68(2), 287\u2013311 (2014)","journal-title":"Algorithmica"},{"key":"1128_CR13","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N.: The two-edge connectivity survivable network problem in planar graphs. In: International Colloquium on Automata, Languages and Programming, pp. 485\u2013501. Springer (2008)","DOI":"10.1007\/978-3-540-70575-8_40"},{"issue":"3","key":"1128_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1541885.1541892","volume":"5","author":"G Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: An $$O(n \\log n)$$ approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms 5(3), 31 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1128_CR15","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"Moses Charikar","year":"2005","unstructured":"Charikar, Moses, Guruswami, Venkatesan, Wirth, Anthony: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360\u2013383 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"1128_CR16","doi-asserted-by":"crossref","unstructured":"Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlation clustering on complete and complete $$k$$-partite graphs. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 219\u2013228 (2015)","DOI":"10.1145\/2746539.2746604"},{"key":"1128_CR17","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Lee, E., Newman, A.: Correlation clustering with Sherali-Adams. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 651\u2013661. IEEE (2022)","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"1128_CR18","unstructured":"Czumaj, A., Lingas, A.: On approximability of the minimum-cost $$k$$-connected spanning subgraph problem. In: Symposium on Discrete Algorithms, pp. 281\u2013290. SIAM (1999)"},{"issue":"2","key":"1128_CR19","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"Erik D Demaine","year":"2006","unstructured":"Demaine, Erik D., Emanuel, Dotan, Fiat, Amos, Immorlica, Nicole: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2), 172\u2013187 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"1128_CR20","volume-title":"Graph Theory. Electronic Library of Mathematics","author":"Reinhard Diestel","year":"2006","unstructured":"Diestel, Reinhard: Graph Theory. Electronic Library of Mathematics. Springer, Berlin (2006)"},{"issue":"3","key":"1128_CR21","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"1128_CR22","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"GN Frederickson","year":"1981","unstructured":"Frederickson, G.N., Ja\u2019Ja\u2019, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"1128_CR23","doi-asserted-by":"crossref","unstructured":"Galluccio, A., Proietti, G.: A faster approximation algorithm for 2-edge-connectivity augmentation. In: International Symposium on Algorithms and Computation, pp. 150\u2013162 (2002)","DOI":"10.1007\/3-540-36136-7_14"},{"issue":"1","key":"1128_CR24","doi-asserted-by":"publisher","first-page":"4-es","DOI":"10.1145\/1217299.1217303","volume":"1","author":"A Gionis","year":"2007","unstructured":"Gionis, A., Mannila, H., Tsaparas, P.: Clustering aggregation. ACM Trans. Knowl. Discov. Data 1(1), 4-es (2007)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"1128_CR25","doi-asserted-by":"crossref","unstructured":"Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. In: Symposium on Discrete Algorithm, pp. 1167\u20131176. ACM (2006)","DOI":"10.1145\/1109557.1109686"},{"key":"1128_CR26","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9, Williamson, D.P.: Improved approximation algorithms for network design problems. In: Symposium on Discrete Algorithms, pp. 223\u2013232. SIAM (1994)"},{"issue":"1","key":"1128_CR27","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"1128_CR28","unstructured":"Jothi, R., Raghavachari, B., Varadarajan, S.: A 5\/4-approximation algorithm for minimum 2-edge-connectivity. In Symposium on Discrete algorithms, pp. 725\u2013734. SIAM (2003)"},{"issue":"2","key":"1128_CR29","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"Samir Khuller","year":"1993","unstructured":"Khuller, Samir, Thurimella, Ramakrishna: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214\u2013225 (1993)","journal-title":"J. Algorithms"},{"issue":"2","key":"1128_CR30","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"Samir Khuller","year":"1994","unstructured":"Khuller, Samir, Vishkin, Uzi: Biconnectivity approximations and graph carvings. J. ACM 41(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"key":"1128_CR31","unstructured":"Kim, S., Nowozin, S., Kohli, P., Yoo, C.D.: Higher-order correlation clustering for image segmentation. In: Advances in Neural Information Processing Systems, pp. 1530\u20131538 (2011)"},{"key":"1128_CR32","unstructured":"Klein, P.N., Mathieu, C., Zhou, H.: Correlation clustering and two-edge-connected augmentation for planar graphs. In: Symposium on Theoretical Aspects of Computer Science, pp. 554\u2013567 (2015)"},{"key":"1128_CR33","unstructured":"Klein, P.N., Mozes, S.: Optimization algorithms for planar graphs. In: preparation, manuscript at http:\/\/planarity.org"},{"key":"1128_CR34","unstructured":"Klein, P.N., Ravi, R.: When cycles collapse: A general approximation technique for constrained two-connectivity problems. In: Integer Programming and Combinatorial Optimization, pp. 39\u201355 (1993)"},{"issue":"3","key":"1128_CR35","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput. 33(3), 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1128_CR36","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TPAMI.2004.1273918","volume":"26","author":"DR Martin","year":"2004","unstructured":"Martin, D.R., Fowlkes, C.C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. Pattern Anal. Mach. Intell. 26(5), 530\u2013549 (2004)","journal-title":"Pattern Anal. Mach. Intell."},{"key":"1128_CR37","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Symposium on Discrete Algorithms, pp. 712\u2013728 (2010)","DOI":"10.1137\/1.9781611973075.58"},{"issue":"2","key":"1128_CR38","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jagm.1999.1005","volume":"32","author":"JS Provan","year":"1999","unstructured":"Provan, J.S., Burk, R.C.: Two-connected augmentation problems in planar graphs. J. Algorithms 32(2), 87\u2013107 (1999)","journal-title":"J. Algorithms"},{"key":"1128_CR39","unstructured":"Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Symposium on Discrete Algorithms, pp. 526\u2013527. SIAM (2004)"},{"issue":"3","key":"1128_CR40","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"David P Williamson","year":"1995","unstructured":"Williamson, David P., Goemans, Michel X., Mihail, Milena, Vazirani, Vijay V.: A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15(3), 435\u2013454 (1995)","journal-title":"Combinatorica"},{"key":"1128_CR41","doi-asserted-by":"crossref","unstructured":"Yarkony, J., Ihler, A., Fowlkes, C. C.: Fast planar correlation clustering for image segmentation. In: European Conference on Computer Vision, vol. 7577, pp. 568\u2013581. Springer (2012)","DOI":"10.1007\/978-3-642-33783-3_41"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01128-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01128-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01128-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:07:49Z","timestamp":1695737269000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01128-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,5]]},"references-count":41,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1128"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01128-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,5]]},"assertion":[{"value":"1 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This submission is in conflict of interest with Vincent Cohen-Addad, who was a PhD student of the second author.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}