Network-design with degree constraints

DOI10.1007/978-3-642-22935-0_25MaRDI QIDQ3088102zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Guy Kortsarz, Zeev Nutov

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

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

Recommendations

• On some network design problems with degree constraints
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Survivable network design with degree or order constraints
• Degree bounded network design with metric costs
• Degree constrained node-connectivity problems

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Additive guarantees for degree-bounded directed network design
• An analysis of the greedy algorithm for the submodular set covering problem
• An approximation algorithm for the directed telephone multicast problem
• Approximating directed weighted-degree constrained networks
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation algorithms for finding low-degree subgraphs
• Generalized submodular cover problems and applications
• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• Improved algorithm for degree bounded survivable network design problem
• Prize-collecting Steiner networks via iterative rounding
• Survivable network design with degree or order constraints

Cited in

(9)

• Design networks with bounded pairwise distance
• Degree-constrained node-connectivity
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Lower bounding techniques for the degree-constrained network design problem
• On some network design problems with degree constraints
• Degree constrained node-connectivity problems
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)
• Network Design with Edge-Connectivity and Degree Constraints
• Approximation algorithms for degree-constrained minimum-cost network-design problems

This page was built for publication: Network-design with degree constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088102)