Balancing Minimum Spanning and Shortest Path Trees

Abstract

This paper give a simple linear-time algorithm that, given a weighted digraph, finds a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the two trees and epsilon > 0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+epsilon times the shortest-path distance, and yet the total weight of the tree is at most 1+2/epsilon times the weight of a minimum spanning tree. This is the best tradeoff possible. The paper also describes a fast parallel implementation.

conference version: ACM-SIAM Symposium on Discrete Algorithms (1993)

Cited by in corpus (7)

• Spatial Networks
• Optimal Traffic Networks
• On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms
• A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
• The Minimum Wiener Connector
• Transitions in spatial networks
• A Parameterized Approximation Algorithm for The Shallow-Light Steiner Tree Problem