neal young / Khuller95Balancing

Algorithmica 14(4):305322(1995); SODA'93This paper has a simple lineartime algorithm to find a spanning tree that simultaneously approximates a shortestpath tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: 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 shortestpath tree is at most \(1+\epsilon\) times the shortestpath 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.Journal version of [1993].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.