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

Original language | English (US) |
---|---|

Pages (from-to) | 305-321 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 14 |

Issue number | 4 |

DOIs | |

State | Published - Oct 1995 |

## Keywords

- Graph algorithms
- Minimum spanning trees
- Parallel algorithms
- Shortest paths

## ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics