Tight approximation algorithm for connectivity augmentation problems

DOI10.1016/j.jcss.2007.05.002zbMath1182.68363OpenAlexW2031552172MaRDI QIDQ931712

Zeev Nutov, Guy Kortsarz

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.05.002

zbMATH Keywords

approximation algorithmconnectivity augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items

Approximating subset \(k\)-connectivity problems ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximating node-connectivity augmentation problems ⋮ Augmenting edge-connectivity between vertex subsets ⋮ Approximating source location and star survivable network problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ A note on Rooted Survivable Networks ⋮ Inapproximability of survivable networks ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Network design via iterative rounding of setpair relaxations
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On shredders and vertex connectivity augmentation
• Edge-connectivity augmentation problems
• Covering symmetric supermodular functions by graphs
• On the minimum local-vertex-connectivity augmentation in graphs
• Independence free graphs and vertex connectivity augmentation
• An analysis of the greedy algorithm for the submodular set covering problem
• Minimal edge-coverings of pairs of sets
• Approximating rooted connectivity augmentation problems
• Design networks with bounded pairwise distance
• Polylogarithmic inapproximability
• Approximation algorithms for network design with metric costs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• A Reduction Method for Edge-Connectivity in Graphs
• Approximation Algorithms for Directed Steiner Problems