T.M. Nicholl, D.T. Lee, et al.
BIT
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.
T.M. Nicholl, D.T. Lee, et al.
BIT
K. Steinhöfel, A. Albrecht, et al.
International Conference on Computer Science and Informatics 1998
P. Widmayer, L. Woo, et al.
Integration, the VLSI Journal
A. Albrecht, C.K. Wong
Neural Processing Letters