Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
From MaRDI portal
Publication:2944499
DOI10.1145/1103963.1103967zbMath1321.68386WikidataQ56077951 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
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
90B10: Deterministic network models in operations research
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Rooted Uniform Monotone Minimum Spanning Trees, An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem, Optimizing the Design of a Wind Farm Collection Network, Solver-free heuristics to retrieve feasible points for offshore wind farm collection system, Improved approximation algorithms for the single-sink buy-at-bulk network design problems, Formulations for designing robust networks. An application to wind power collection, The \((K, k)\)-capacitated spanning tree problem, Minimum spanning trees of random geometric graphs with location dependent weights, Approximation algorithms for solving the line-capacitated minimum Steiner tree problem, On the edge capacitated Steiner tree problem, Empirical study of exact algorithms for the multi-objective spanning tree, Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below, Approximating Airports and Railways