Balancing minimum spanning and shortest path trees

Samir Khuller*, Balaji Raghavachari, Neal Young

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

57 Scopus citations

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 languageEnglish (US)
Pages243-250
Number of pages8
StatePublished - Jan 1 1993
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Balancing minimum spanning and shortest path trees'. Together they form a unique fingerprint.

Cite this