Campus Event Calendar
Event Entry
What and Who
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs
Hang Zhou
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 8 October 2015
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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 union 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.
This is joint work with Philip Klein and Claire Mathieu.
Contact
Hang Zhou
+33 623559304
--email hidden
passcode not visible
logged in users only
Hang Zhou, 09/28/2015 14:28 -- Created document.