Approximation algorithms for degree-constrained minimum-cost network-design problems

DOI10.1007/s00453-001-0038-2zbMath0980.68139OpenAlexW1998141189MaRDI QIDQ5946123

Harry B. III Hunt, S. S. Ravi, R. Ravi, Daniel J. Rosenkrantz, M. V. Maranthe

Publication date: 2001

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0038-2

zbMATH Keywords

Steiner treenetwork-design problems

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10)

Related Items (19)

ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ Small degree out‐branchings ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ The maximum degree \& diameter-bounded subgraph and its applications ⋮ A Spectral Approach to Network Design ⋮ Chain-constrained spanning trees ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ The Maximum Binary Tree Problem. ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ Lower bounding techniques for the degree-constrained network design problem ⋮ The maximum binary tree problem ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Degree-bounded minimum spanning trees ⋮ Unnamed Item

This page was built for publication: Approximation algorithms for degree-constrained minimum-cost network-design problems