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

DOI10.1007/s00453-023-01128-wOpenAlexW4372319455MaRDI QIDQ6046943

Hang Zhou, Claire Mathieu, Philip N. Klein

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4941/

zbMATH Keywords

planar graphspolynomial-time approximation schemecorrelation clustering2-edge-connected augmentation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Correlation clustering
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Correlation clustering in general weighted graphs
• Clustering with qualitative information
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• Correlation clustering with a fixed number of clusters
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Two-Connected Augmentation Problems in Planar Graphs
• Biconnectivity approximations and graph carvings
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
• Aggregating inconsistent information

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