On finding Steiner vertices. (English) Zbl 0644.90095
Summary: Given a graph \(G=(V,E)\), finding the Steiner tree in G for some set of special vertices V’\(\subset V\) is equivalent to finding the minimum spanning tree in the subgraph of G induced by V’\(\cup V''\), where V” is the set of Steiner vertices. We consider ways of deciding which vertices of V are in V” and compare the performance of various heuristic algorithms.
MSC:
| 90C35 | Programming involving graphs or networks |
| 65K05 | Numerical mathematical programming methods |
References:
| [1] | Beasley, Networks 14 pp 147– (1984) |
| [2] | Heuristic algorithms for finding Steiner vertices. School of Computing Studies and Accountancy, University of East Anglia, Norwich (1984). |
| [3] | A note on two problems in connection with graphs. Numerische Mathematik (1959) 269–271. · Zbl 0092.16002 |
| [4] | and , The Steiner problem in graphs. Networks (1972) 195–207. · Zbl 0229.05125 |
| [5] | Floyd, CACM 5 pp 345– (1962) · doi:10.1145/367766.368168 |
| [6] | Foulds, Eng. Opt. 7 pp 1– (1983) |
| [7] | Garey, Proc. of the 8th Annual ACM Symposium on Theory of Computing 10-22 (1976) |
| [8] | Garey, SIAM J. Appl. Math. 32 pp 835– (1977) |
| [9] | Garey, SIAM J. Appl. Math. 32 pp 826– (1977) |
| [10] | Hakimi, Networks 1 pp 113– (1971) |
| [11] | Reducibility among combinatorial problems. I. Complexity of Computer Computations ( and , Eds.). Plenum Press, New York (1972) 85–104. · doi:10.1007/978-1-4684-2001-2_9 |
| [12] | Kou, Acta Informatica 15 pp 141– (1981) |
| [13] | Kruskal, Proc. Am. Math Soc. 7 pp 48– (1956) |
| [14] | Levin, Soviet Math. Dokl. 12 pp 1477– (1971) |
| [15] | Prim, Bell Systems Tech. J. 36 pp 1389– (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [16] | Rayward-Smith, Int. J. Math. Educ. Sci. Technol. 14 pp 15– (1983) |
| [17] | Shore, Networks 12 pp 323– (1982) |
| [18] | Takahashi, Math. Japonica 6 pp 573– (1980) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
