Balancing Steiner trees and shortest path trees online

Conference Paper

Given a weighted undirected graph G(V, E) and a subset R of V, we present an online algorithm for finding a Steiner tree on R that simultaneously approximates the shortest path tree and the minimum weight Steiner tree. The cost of the tree we construct is within an O(log |R|) factor of the optimal cost, and the path length from the root to any terminal is at most O(1) times the shortest path length. The algorithm needs to perform at most one reroute for each node in the tree.

Duke Authors

Cited Authors

  • Goel, A; Munagala, K

Published Date

  • January 1, 2000

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 562 - 563

Citation Source

  • Scopus