On some network design problems with degree constraints

DOI10.1016/J.JCSS.2013.01.019MaRDI QIDQ355516zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Guy Kortsarz, Zeev Nutov

Publication date 24 July 2013

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2013.01.019

zbMATH Keywords

approximation algorithmsnetwork designdegree-constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• Network-design 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

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A factor 2 approximation algorithm for the generalized Steiner network 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 Directed Steiner Problems
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for finding low-degree subgraphs
• Degree-constrained node-connectivity
• Generalized submodular cover problems and applications
• Improved algorithm for degree bounded survivable network design problem
• Iterative methods in combinatorial optimization.
• Network-design with degree constraints
• On approximation algorithms for the terminal Steiner tree problem
• On the full and bottleneck full Steiner tree problems
• On the terminal Steiner tree problem.
• Prize-collecting Steiner network problems
• Prize-collecting Steiner networks via iterative rounding
• Survivable network design with degree or order constraints

Cited in

(15)

• Approximating bounded-degree spanning trees and connected factors with leaves
• Network Design with Edge-Connectivity and Degree Constraints
• Approximation algorithms for connected graph factors of minimum weight
• Lower bounding techniques for the degree-constrained network design problem
• Network-design with degree constraints
• The maximum binary tree problem
• Heuristics for the network design problem with connectivity requirements
• Binary Steiner trees: structural results and an exact solution approach
• A unified algorithm for degree bounded survivable network design
• A multivariate analysis of the strict terminal connection problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• The telephone k-multicast problem
• The Maximum Binary Tree Problem.
• The telephone \(k\)-multicast problem
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)

This page was built for publication: On some network design problems with degree constraints

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