Path-distance heuristics for the Steiner problem in undirected networks

Y. P. Aneja, An integer linear programming approach to the Steiner problem in graphs,Networks 10 (1980), 167–178.

A. Balakrishnan and N. R. Patel, Problem reduction methods and a tree generation algorithm for the Steiner network problem,Networks 17 (1987), 65–85.

J. E. Beasley, An algorithm for the Steiner problem in graphs,Networks 14 (1984), 147–159.

J. E. Beasley, An SST-based algorithm for the Steiner problem on graphs,Networks 19 (1989), 1–16.

N. P. Chen, New algorithm for Steiner tree on graphs,IEEE Symp. on Circuits and Systems, 1983, pp. 1217–1219.

S. E. Dreyfus and R. A. Wagner, The Steiner problem in graphs,Networks 1 (1971), 195–207.

C. W. Duin and A. Volgenant, Reduction tests for the Steiner problem in graphs,Networks 19 (1989), 549–567.

C. El-Arbi, Une heuristique pour le probleme de l'arbre de Steiner,RAIRO Rech. Opér. 12 (1978), 202–212.

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

S. L. Hakimi, Steiner problem in graphs and its implications,Networks 1 (1971), 113–133.

L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner trees,Acta Inform. 15 (1981), 141–145.

J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proc. Amer. Math. Soc. 7 (1956), 48–50.

K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs,Inform. Process. Lett. 27 (1988), 125–128.

J. Plesnik, A bound for the Steiner problem in graphs,Math. Solvaca 31 (1981), 155–163.

R. C. Prim, Shortest connection networks and some generalizations,Bell System Tech. J. 36 (1957), 1389–1401.

V. J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs,Internat. J. Math. Ed. Sci. Tech. 14 (1983), 15–23.

V. J. Rayward-Smith and A. Clare, On finding Steiner vertices,Networks 16 (1986), 283–294.

C. Schiemangk, Thermodynamically motivated simulation for solving the Steiner tree problem and the optimization of interacting path systems, in A. Iwainsky (ed.),Optimization of Connection Structures in Graphs, CICIP, Berlin, 1985, pp. 91–120.

M. L. Shore, L. R. Foulds, and P. B. Gibbons, An algorithm for the Steiner problem in graphs,Networks 12 (1982), 323–333.

H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs,Math. Japon. 24 (1980), 573–577.

B. M. Waxman and M. Imase, Worst-case performance of Rayward-Smith's Steiner tree heuristics,Inform. Process. Lett. 29 (1988), 283–287.

P. Widmayer, On approximation algorithms for Steiner's problem in graphs, in G. Tinhofer and G. Schmidt (eds.),Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 246, Springer-Verlag, Berlin, 1986, pp. 17–28.

P. Winter, Steiner problem in networks: a survey,Networks 17 (1987), 129–167.

R. T. Wong, A dual ascent approach for the Steiner tree problem on a directed graph,Math. Programming 28 (1984), 271–287.

Y. F. Wu, P. Widmayer, and C. K. Wong, A faster approximation algorithm for the Steiner problem in graphs,Acta Inform. 23 (1986), 223–229.