The \((K, k)\)-capacitated spanning tree problem

DOI10.1016/j.disopt.2012.08.002zbMath1254.90268MaRDI QIDQ1926491

Esther M. Arkin, Refael Hassin, Nili Guttmann-Beck

Publication date: 28 December 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.08.002

zbMATH Keywords

approximation algorithms; minimum capacitated spanning tree

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Cites Work

• Unnamed Item
• Unnamed Item
• Topological design of telecommunication networks --- local access design methods
• Analysis of heuristics for the design of tree networks
• Survivable network design: the capacitated minimum spanning network problem
• An improved approximation algorithm for capacitated multicast routings in networks
• The Multilevel Capacitated Minimum Spanning Tree Problem
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Approximating minimum bounded degree spanning trees to within one of optimal
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• The complexity of the capacitated tree problem
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds