Improved algorithm for degree bounded survivable network design problem

DOI10.1007/978-3-642-13731-0_38zbMATH Open1285.68124arXiv0911.4544OpenAlexW3122273056MaRDI QIDQ3569909FDOQ3569909

Authors: Anand Louis, Nisheeth K. Vishnoi 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (10)

• Network-design with degree constraints
• On some network design problems with degree constraints
• Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
• Binary Steiner trees: structural results and an exact solution approach
• 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
• Approximation Algorithms for Multi-budgeted Network Design Problems
• Degree constrained node-connectivity problems
• A Spectral Approach to 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)