Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
From MaRDI portal
Publication:2949211
DOI10.1137/13094503XzbMath1322.05082arXiv1203.3578OpenAlexW2174245573MaRDI QIDQ2949211
Takuro Fukunaga, R. Ravi, Zeev Nutov
Publication date: 8 October 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1203.3578
Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (6)
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ A Spectral Approach to Network Design ⋮ Degree constrained node-connectivity problems ⋮ Approximating minimum power edge-multi-covers ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generalizations of network design problems with degree bounds
- Approximating minimum-cost edge-covers of crossing biset-families
- Degree constrained node-connectivity problems
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Network design via iterative rounding of setpair relaxations
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Rooted \(k\)-connections in digraphs
- Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
- An application of submodular flows
- Approximating node connectivity problems via set covers
- Independence free graphs and vertex connectivity augmentation
- Minimal edge-coverings of pairs of sets
- A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
- Approximating subset \(k\)-connectivity problems
- Degree bounded matroids and submodular flows
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Iterative Methods in Combinatorial Optimization
- Network-Design with Degree Constraints
- Improved Algorithm for Degree Bounded Survivable Network Design Problem
- Survivable Network Design with Degree or Order Constraints
- Additive Guarantees for Degree-Bounded Directed Network Design
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Additive Approximation for Bounded Degree Survivable Network Design
- A Unified Algorithm for Degree Bounded Survivable Network Design
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- Approximating k-node Connected Subgraphs via Critical Graphs
This page was built for publication: Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
