caa a22 4500 467989818 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900301xx s 000 0 eng 10.1007/BF00264613 doi (NATIONALLICENCE)springer-10.1007/BF00264613 Kou Lawrence Department of Electrical Engineering and Computer Science, Computer Science Division, University of California, 95616, Davis, Davis, CA, USA aut On efficient implementation of an approximation algorithm for the Steiner tree problem [Elektronische Daten] [Lawrence Kou] Summary: This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1−1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E g¦+¦V g−S¦log¦V g−S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log β(M,¦V g−S¦)) time for sparse graph G, where E g is the set of edges in G, Vg is the set of vertices in G, M = min {¦E g, (¦V g−S¦−1)2/2} and β(x,y) = min {i¦log(i) y ≦ x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V g¦ vertices and ¦E g¦ edges and the minimum spanning tree of a graph with ¦V g−S¦ vertices and M edges. Springer-Verlag, 1990 Acta Informatica Springer-Verlag 27/4(1990-03-01), 369-380 0001-5903 27:4<369 1990 27 236 https://doi.org/10.1007/BF00264613 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00264613 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Kou Lawrence Department of Electrical Engineering and Computer Science, Computer Science Division, University of California, 95616, Davis, Davis, CA, USA aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 27/4(1990-03-01), 369-380 0001-5903 27:4<369 1990 27 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer