Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design

DOI10.1145/1103963.1103967zbMath1321.68386OpenAlexW2004240896WikidataQ56077951 ScholiaQ56077951MaRDI QIDQ2944499

Balaji Raghavachari, Raja Jothi

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1103963.1103967

zbMATH Keywords

network designapproximation algorithmsminimum spanning treesspanning trees

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (13)

Rooted Uniform Monotone Minimum Spanning Trees ⋮ Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below ⋮ Approximating Airports and Railways ⋮ The \((K, k)\)-capacitated spanning tree problem ⋮ Optimizing the Design of a Wind Farm Collection Network ⋮ Solver-free heuristics to retrieve feasible points for offshore wind farm collection system ⋮ On the edge capacitated Steiner tree problem ⋮ Formulations for designing robust networks. An application to wind power collection ⋮ Minimum spanning trees of random geometric graphs with location dependent weights ⋮ Empirical study of exact algorithms for the multi-objective spanning tree ⋮ Improved approximation algorithms for the single-sink buy-at-bulk network design problems ⋮ An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

This page was built for publication: Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design