Improved algorithm for degree bounded survivable network design problem
From MaRDI portal
Publication:3569909
Abstract: We consider the Degree-Bounded Survivable Network Design Problem: the objective is to find a minimum cost subgraph satisfying the given connectivity requirements as well as the degree bounds on the vertices. If we denote the upper bound on the degree of a vertex v by b(v), then we present an algorithm that finds a solution whose cost is at most twice the cost of the optimal solution while the degree of a degree constrained vertex v is at most 2b(v) + 2. This improves upon the results of Lau and Singh and that of Lau, Naor, Salavatipour and Singh.
Recommendations
- A unified algorithm for degree bounded survivable network design
- A unified algorithm for degree bounded survivable network design
- Degree constrained node-connectivity problems
- Additive Approximation for Bounded Degree Survivable Network Design
- Survivable network design with degree or order constraints
Cited in
(12)- Network-design with degree constraints
- On some network design problems with degree constraints
- Binary Steiner trees: structural results and an exact solution approach
- A unified algorithm for degree bounded survivable network design
- Approximation algorithms for multi-budgeted network design problems
- A unified algorithm for degree bounded survivable network design
- Survivable network design with degree or order constraints
- Additive Approximation for Bounded Degree Survivable Network Design
- Degree constrained node-connectivity problems
- A Spectral Approach to Network Design
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
This page was built for publication: Improved algorithm for degree bounded survivable network design problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569909)
