Network-Design with Degree Constraints

DOI10.1007/978-3-642-22935-0_25zbMath1343.68185OpenAlexW195354029MaRDI 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

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

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

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

This page was built for publication: Network-Design with Degree Constraints