Approximation algorithms for connectivity augmentation problems

DOI10.1007/978-3-030-79416-3_19OpenAlexW3177131004MaRDI QIDQ2117100

Zeev Nutov

Publication date: 21 March 2022

Full work available at URL: https://arxiv.org/abs/2009.13257

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Node connectivity augmentation via iterative randomized rounding ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for minimum-cost vertex-connectivity problems
• Local edge-connectivity augmentation in hypergraphs is NP-complete
• Covering a laminar family by leaf to leaf links
• Augmenting hypergraphs by edges of size two
• Covering symmetric supermodular functions by graphs
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• A unifying approach to splitting-off
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• On the tree augmentation problem
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
• Parameterized Algorithms to Preserve Connectivity
• Improved approximation for tree augmentation: saving by rewiring
• Steiner Tree Approximation via Iterative Randomized Rounding

This page was built for publication: Approximation algorithms for connectivity augmentation problems