A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
From MaRDI portal
Publication:4962787
DOI10.1145/1497290.1497297zbMath1398.68670OpenAlexW2057915045MaRDI QIDQ4962787
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.151.4596
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (18)
An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On the tree augmentation problem ⋮ 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 ⋮ A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\) ⋮ 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 ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ 2-node-connectivity network design ⋮ Covering a laminar family by leaf to leaf links ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ 2-node-connectivity network design
This page was built for publication: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
