Abstract
Efficient algorithms are known for computing a minimum spanning tree, or a shortest path tree (with a fixed vertex as the root). The weight of a shortest path tree can be much more than the weight of a minimum spanning tree. Conversely, the distance between the root and any vertex in a minimum spanning tree may be much more than the distance between the two vertices in the graph. Consider the problem of balancing between the two kinds of trees: Does every graph contain a tree that is `light' (at most a constant times heavier than the minimum spanning tree), such that the distance from the root to any vertex in the tree is no more than a constant times the true distance? This paper answers the question in the affirmative. It is shown that there is a continuous tradeoff between the two parameters. For every γ>0, there is a tree in the graph whose total weight is at most 1+√2/γ times the weight of a minimum spanning tree, such that the distance in the tree between the root and any vertex is at most 1+√2γ times the true distance. Efficient sequential and parallel algorithms achieving these factors are provided. The algorithms are shown to be optimal in two ways. First, it is shown that no algorithm can achieve better factors in all graphs, because there are graphs that do not have better trees. Second, it is shown that even on a per-graph basis, finding trees that achieve better factors is NP-hard.
Original language | English (US) |
---|---|
Pages | 243-250 |
Number of pages | 8 |
State | Published - 1993 |
Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |
Other
Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
City | Austin, TX, USA |
Period | 1/25/93 → 1/27/93 |
ASJC Scopus subject areas
- General Engineering