Approximation algorithms for connectivity augmentation problems
From MaRDI portal
Publication:2117100
DOI10.1007/978-3-030-79416-3_19OpenAlexW3177131004MaRDI QIDQ2117100FDOQ2117100
Authors: Zeev Nutov 
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2009.13257
Cites Work
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Connections in combinatorial optimization
- Steiner tree approximation via iterative randomized rounding
- A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- Covering a laminar family by leaf to leaf links
- An approximation algorithm for minimum-cost vertex-connectivity problems
- Covering symmetric supermodular functions by graphs
- Approximating connectivity augmentation problems
- Augmenting hypergraphs by edges of size two
- Improved approximation for tree augmentation: saving by rewiring
- Local edge-connectivity augmentation in hypergraphs is NP-complete
- Title not available (Why is that?)
- A unifying approach to splitting-off
- On the tree augmentation problem
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- Title not available (Why is that?)
- Parameterized algorithms to preserve connectivity
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
- On the Cycle Augmentation Problem: hardness and approximation algorithms
- Title not available (Why is that?)
Cited In (17)
- On algebraic connectivity augmentation
- Node connectivity augmentation via iterative randomized rounding
- Dual-based approximation algorithms for cut-based network connectivity problems
- Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
- A note on the vertex-connectivity augmentation problem
- Approximating node-connectivity augmentation problems
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- Minimum Cardinality Point-to-point Connectivity Augmentation Problem
- Approximation algorithms for graph augmentation
- Approximating connectivity augmentation problems
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
- Approximating Minimum Cost Connectivity Orientation and Augmentation
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
- Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
- Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
This page was built for publication: Approximation algorithms for connectivity augmentation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117100)
