Balancing Minimum Spanning and Shortest Path Trees
<|reference_start|>Balancing Minimum Spanning and Shortest Path Trees: 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.<|reference_end|>
@article{khuller2002balancing,
    title={Balancing Minimum Spanning and Shortest Path Trees},
    author={Samir Khuller, Balaji Raghavachari, Neal E. Young},
    journal={Algorithmica 14(4):305-322 (1995)},
    year={2002},
    doi={10.1007/BF01294129},
    archivePrefix={arXiv},
    eprint={cs/0205045},
    primaryClass={cs.DS cs.DM}
}