Balancing Steiner trees and shortest path trees online
Publication
, Conference
Goel, A; Munagala, K
Published in: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
January 1, 2000
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 Scholars
Published In
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publication Date
January 1, 2000
Start / End Page
562 / 563
Citation
APA
Chicago
ICMJE
MLA
NLM
Goel, A., & Munagala, K. (2000). Balancing Steiner trees and shortest path trees online. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 562–563).
Goel, A., and K. Munagala. “Balancing Steiner trees and shortest path trees online.” In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 562–63, 2000.
Goel A, Munagala K. Balancing Steiner trees and shortest path trees online. In: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. 2000. p. 562–3.
Goel, A., and K. Munagala. “Balancing Steiner trees and shortest path trees online.” Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 2000, pp. 562–63.
Goel A, Munagala K. Balancing Steiner trees and shortest path trees online. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. 2000. p. 562–563.
Published In
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publication Date
January 1, 2000
Start / End Page
562 / 563