Balancing Minimum Spanning and Shortest Path Trees

Details Balancing Minimum Spanning and Shortest Path Trees Balancing Minimum Spanning and Shortest Path Trees

2002-05-18

arxiv.org/abs/cs/0205045v1

Algorithmica 14(4):305-322 (1995)

Computer Science

Data Structures and Algorithms

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Balancing Minimum Spanning and Shortest Path Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Balancing Minimum Spanning and Shortest Path Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balancing Minimum Spanning and Shortest Path Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599179