TY - GEN
T1 - Correlation clustering and two-edge-connected augmentation for planar graphs
AU - Klein, Philip N.
AU - Mathieu, Claire
AU - Zhou, Hang
N1 - Publisher Copyright:
© 2015 LIPICS.
PY - 2015/2/1
Y1 - 2015/2/1
N2 - 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 ∪ 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.
AB - 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 ∪ 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.
KW - Correlation clustering
KW - Planar graphs
KW - Polynomialtime approximation scheme
KW - Two-edge-connected augmentation
UR - https://www.scopus.com/pages/publications/84923883629
U2 - 10.4230/LIPIcs.STACS.2015.554
DO - 10.4230/LIPIcs.STACS.2015.554
M3 - Conference contribution
AN - SCOPUS:84923883629
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 554
EP - 567
BT - 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
A2 - Mayr, Ernst W.
A2 - Ollinger, Nicolas
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
Y2 - 4 March 2015 through 7 March 2015
ER -