Approximation algorithms for the optimal \(p\)-source communication spanning tree
From MaRDI portal
Publication:1887037
DOI10.1016/j.dam.2003.10.002zbMath1055.05145OpenAlexW2088257048MaRDI QIDQ1887037
Publication date: 23 November 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2003.10.002
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Tight bounds from a path based formulation for the tree of hub location problem ⋮ An improved algorithm for the \(k\)-source maximum eccentricity spanning trees ⋮ Models and algorithms for network reduction ⋮ On the intercluster distance of a tree metric ⋮ General network design: a unified view of combined location and network design problems ⋮ The swap edges of a multiple-sources routing tree
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- Approximation algorithms for some optimum communication spanning tree problems
- Approximation algorithms for the shortest total path length spanning tree problem
- Undirected single-source shortest paths with positive integer weights in linear time
- Optimum Communication Spanning Trees
- Worst-Case Analysis of Network Design Problem Heuristics
- The complexity of the network design problem
- A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
- Light graphs with small routing cost
- Exact algorithms for minimum routing cost trees
- A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- The complexity of theorem-proving procedures
This page was built for publication: Approximation algorithms for the optimal \(p\)-source communication spanning tree
