2026-08-15T22:59:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4941 2024-03-06T10:35:36Z ddc:004 open_access

Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs Klein, Philip N. Mathieu, Claire Zhou, Hang correlation clustering two-edge-connected augmentation polynomial-time approximation scheme planar graphs In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or - according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible. In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R\cup S. For planar graphs, we prove that correlation clustering reduces to two-edge-connected augmentation, and that both problems have a polynomial-time approximation scheme. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip N. Klein and Claire Mathieu and Hang Zhou 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.554 urn:nbn:de:0030-drops-49411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.554 eng https://creativecommons.org/licenses/by/3.0/legalcode