Balancing Steiner trees and shortest path trees online
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.
- Goel, A; Munagala, K
- January 1, 2000
- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page
- 562 - 563