D.T. Lee, C.K. Wong
ACM Transactions on Database Systems (TODS)
We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1-1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(|E|log|V|) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(|S||V|2), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach. © 1986 Springer-Verlag.
D.T. Lee, C.K. Wong
ACM Transactions on Database Systems (TODS)
Howard H. Chen, C.K. Wong
CICC 1992
D.T. Lee, C.K. Wong
Acta Informatica
Ashok K. Chandra, D.S. Hirschberg, et al.
Theoretical Computer Science