Skip to main content
eScholarship
Open Access Publications from the University of California

Balancing minimum spanning trees and shortest-path trees

  • Author(s): Khuller, S
  • Raghavachari, B
  • Young, N
  • et al.

Published Web Location

https://arxiv.org/abs/cs/0205045
No data is associated with this publication.
Abstract

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a γ>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+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex. © 1995 Springer-Verlag New York Inc.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item