Network-Design with Degree Constraints

DOI10.1007/978-3-642-22935-0_25zbMath1343.68185MaRDI QIDQ3088102

Rohit Khandekar, Zeev Nutov, Guy Kortsarz

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_25

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

On some network design problems with degree constraints, Degree constrained node-connectivity problems, Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

Cites Work

• Unnamed Item
• Approximating directed weighted-degree constrained networks
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Generalized submodular cover problems and applications
• An analysis of the greedy algorithm for the submodular set covering problem
• An approximation algorithm for the directed telephone multicast problem
• Approximating minimum bounded degree spanning trees to within one of optimal
• Prize-Collecting Steiner Networks via Iterative Rounding
• 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
• Bicriteria Network Design Problems
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation algorithms for finding low-degree subgraphs