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

DOI10.1007/S00453-023-01128-WOpenAlexW4372319455MaRDI QIDQ6046943FDOQ6046943

Authors: Philip N. Klein, Claire Mathieu, Hang Zhou 

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/

Recommendations

• Correlation clustering and two-edge-connected augmentation for planar graphs
• scientific article; zbMATH DE number 1500683
• Planarity-preserving clustering and embedding for large planar graphs
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• scientific article; zbMATH DE number 1187145
• Subgraph induced planar connectivity augmentation (extended abstract)
• scientific article; zbMATH DE number 2084266
• Augmenting the connectivity of planar and geometric graphs
• Augmenting the connectivity of planar and geometric graphs
• Two-Connected Augmentation Problems in Planar Graphs

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

• Correlation clustering with noisy input
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Clustering with qualitative information
• Aggregating inconsistent information: ranking and clustering
• Correlation clustering
• Title not available (Why is that?)
• Title not available (Why is that?)
• Biconnectivity approximations and graph carvings
• Title not available (Why is that?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Correlation clustering in general weighted graphs
• Title not available (Why is that?)
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Correlation clustering, maximizing agreements via semidefinite programming
• An O ( n log n ) approximation scheme for Steiner tree in planar graphs
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Approximation Algorithms for Graph Augmentation
• Correlation clustering with a fixed number of clusters
• Approximation Algorithms for Several Graph Augmentation Problems
• A primal-dual approximation algorithm for generalized Steiner network problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Two-Connected Augmentation Problems in Planar Graphs
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
• A polynomial-time approximation scheme for planar multiway cut
• Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
• Correlation clustering and two-edge-connected augmentation for planar 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 Q6046943)