An improved algorithm for the \(k\)-source maximum eccentricity spanning trees

DOI10.1016/j.dam.2003.12.004zbMath1058.05020OpenAlexW1968783677MaRDI QIDQ1887071

Bang Ye Wu

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.12.004

zbMATH Keywords

distance

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Minimax flow tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The complexity of minimizing certain cost metrics for \(k\)-source spanning trees.
• Multi-source spanning trees: Algorithms for minimizing source eccentricities.
• Approximation algorithms for some optimum communication spanning tree problems
• Approximation algorithms for the shortest total path length spanning tree problem
• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• Undirected single-source shortest paths with positive integer weights in linear time
• Optimum Communication Spanning Trees
• The complexity of the network design problem
• A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning 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

This page was built for publication: An improved algorithm for the \(k\)-source maximum eccentricity spanning trees