Correlation clustering and two-edge-connected augmentation for planar graphs

DOI10.4230/LIPICS.STACS.2015.554MaRDI QIDQ2955023zbMATH OpenFDO

Authors Claire Mathieu, Hang Zhou, Philip N. Klein

Publication date 24 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2015.554

zbMATH Keywords

correlation clusteringplanar graphspolynomial-time approximation schemetwo-edge-connected augmentation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Correlation clustering in general weighted graphs
• Algorithms - ESA 2003
• A PTAS for the Cluster Editing Problem on Planar Graphs
• Two-Connected Augmentation Problems in Planar Graphs
• Correlation clustering with partial information

Cited in

(9)

• A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• A polyhedral study of lifted multicuts
• A PTAS for the Cluster Editing Problem on Planar Graphs
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Correlation clustering and two-edge-connected augmentation for planar graphs
• Approximating maximum integral multiflows on bounded genus graphs
• Approximating maximum integral multiflows on bounded genus graphs

This page was built for publication: Correlation clustering and two-edge-connected augmentation for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955023)