# Balancing Minimum Spanning and Shortest Path Trees

Preprint · Samir Khuller, Balaji Raghavachari, Neal E. Young

- Archive id: arxiv:cs/0205045
- Published: 2002-05-18
- Venue: Algorithmica 14(4):305-322 (1995)
- DOI: https://doi.org/10.1007/bf01294129
- arXiv: https://arxiv.org/abs/cs/0205045
- Citations: 9
- Source URL: https://arxiv.org/abs/cs/0205045
- PDF: https://arxiv.org/pdf/cs/0205045
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.