A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
From MaRDI portal
Publication:4962218
DOI10.1145/2786981zbMath1398.68679arXiv1507.02799OpenAlexW2287418059MaRDI QIDQ4962218
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.02799
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (23)
An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ Flexible Graph Connectivity ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ Plane augmentation of plane graphs to meet parity constraints ⋮ On the tree augmentation problem ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Approximating (unweighted) tree augmentation via lift-and-project. II ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ 2-node-connectivity network design ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ Approximation algorithms for connectivity augmentation problems ⋮ 2-node-connectivity network design ⋮ Flexible graph connectivity
This page was built for publication: A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
