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

DOI10.1016/J.DAM.2003.12.004MaRDI QIDQ1887071zbMATH OpenOpenAlexFDO

Authors 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) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Multi-source spanning trees: Algorithms for minimizing source eccentricities.
• Algorithms and Computation
• Approximation algorithms for somek-source shortest paths spanning tree problems
• scientific article; zbMATH DE number 5228
• On the approximability of some maximum spanning tree problems
• On the approximability of some Maximum Spanning Tree Problems
• Better approximation algorithms for the maximum internal spanning tree problem
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• An algorithm for \(k^{\text{th}}\) minimum spanning tree

Cites work

• A note on two problems in connexion with graphs
• 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
• Approximation algorithms for some optimum communication spanning tree problems
• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• Approximation algorithms for the shortest total path length spanning tree problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimum eccentricity multicast trees
• Multi-source spanning trees: Algorithms for minimizing source eccentricities.
• Optimum Communication Spanning Trees
• The complexity of minimizing certain cost metrics for k-source spanning trees.
• The complexity of the network design problem
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(3)

• Multi-source spanning trees: Algorithms for minimizing source eccentricities.
• Minimax flow tree problems
• Algorithms and Computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887071)