On some network design problems with degree constraints
From MaRDI portal
Publication:355516
DOI10.1016/j.jcss.2013.01.019zbMath1269.68069OpenAlexW2052113818MaRDI QIDQ355516
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
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (8)
Heuristics for the network design problem with connectivity requirements ⋮ A unified algorithm for degree bounded survivable network design ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ The Maximum Binary Tree Problem. ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ The maximum binary tree problem ⋮ A multivariate analysis of the strict terminal connection problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating directed weighted-degree constrained networks
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On approximation algorithms for the terminal Steiner tree problem
- Generalized submodular cover problems and applications
- An analysis of the greedy algorithm for the submodular set covering problem
- On the terminal Steiner tree problem.
- An approximation algorithm for the directed telephone multicast problem
- Degree-Constrained Node-Connectivity
- On the Full and Bottleneck Full Steiner Tree Problems
- Iterative Methods in Combinatorial Optimization
- Network-Design with Degree Constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Prize-Collecting Steiner Networks via Iterative Rounding
- Prize-Collecting Steiner Network Problems
- 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
- Approximation Algorithms for Directed Steiner Problems
This page was built for publication: On some network design problems with degree constraints
