×

Steiner problem in networks: A survey. (English) Zbl 0646.90028

Summary: The problem of determining a minimum cost connected network (i.e., weighted graph) G that spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.

MSC:

90B05 Inventory, storage, reservoirs
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C10 Integer programming
90B10 Deterministic network models in operations research
90C39 Dynamic programming
90C09 Boolean programming
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
90B15 Stochastic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, Networks 7 pp 37– (1977)
[2] Aneja, Networks 10 pp 167– (1980)
[3] and , Characterization and recognition of partial k-trees. Tech. Rep. TRITA-NA-8402, Dept. of Numerical Analysis and Computing Science, The Royal Inst. of Technology, Stockholm, Sweden (1984).
[4] and , Linear time algorithms for NP-hard problems on graphs embedded in k-trees. Tech. Rep. TRITA-NA-8404, Dept. of Numerical Analysis and Computing Science, The Royal Inst. of Technology, Stockholm, Sweden (1984). · Zbl 0527.68049
[5] and , Problem reduction methods and a tree generation algorithm for the Steiner network problem. Unpublished paper (1985).
[6] Beasley, Networks 14 pp 147– (1984)
[7] An SST-based algorithm for the Steiner problem in graphs. Tech. Rep., Dept. of Man. Science, Imperial College, London (1985).
[8] Bellman, Q. Appl. Math. 16 pp 87– (1958)
[9] Bellmore, Manag. Sci. 18 pp 194– (1971)
[10] Boyce, ACM Trans. on Math. Software 3 pp 359– (1977)
[11] and , STEINER72: An improved version of the minimal network problem. Tech. Rep. No. 35, Comp. Sci. Res. Ctr. Bell Laboratories, Murray Hill, N.J. (undated).
[12] Chang, J. ACM 19 pp 669– (1972)
[13] Worst-case analysis of new heuristic for the traveling salesman problem. Tech. Rep. TR-GSIA, Carnegie-Mellon Univ. Pittsburgh, Pa. (1976).
[14] and , Network synthesis with connectivity constraints-a survey. In (Ed.) Operational Research ’81. North-Holland, Amsterdam (1981) 705–723.
[15] Chung, Geometriae Dedicata 11 pp 353– (1981)
[16] Chung, Networks 9 pp 19– (1979)
[17] and , Computation of Steiner minimal trees. In Welsh and Woddall (Eds.), Combinatorics. Inst. Math. Appl. (1972) 52–71.
[18] Dijkstra, Numer. Math. 1 pp 269– (1959)
[19] Dionne, Networks 9 pp 37– (1979)
[20] Dreyfus, Networks 1 pp 195– (1971)
[21] El-Arbi, Operations Research 12 pp 207– (1978)
[22] , and , Send-and-split method for minimum-concave-cost network flows. Unpublished paper (1985).
[23] Farber, Discrete Math. 43 pp 173– (1983)
[24] Farley, SIAM J. Alg. Discr. Meth. 1 pp 70– (1980)
[25] Fisher, Man. Sci. 27 pp 1– (1981) · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[26] Floyd, Comm. ACM 5 pp 345– (1962)
[27] Foulds, Optima 10 pp 1– (1983)
[28] Foulds, J. Comb. Inf. Syst. Sci. 6 pp 215– (1981)
[29] Foulds, Adv. Appl. Math. 3 pp 43– (1982)
[30] Foulds, Eng. Opt. 7 pp 7– (1983)
[31] Application of linear graph theory to printed circuits. Proc. Asilomar Conf. Systems and Circuits (1967) 721–728.
[32] Gabow, SIAM J. Comput. 6 pp 139– (1977)
[33] Garey, SIAM J Appl. Math. 32 pp 826– (1977)
[34] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). · Zbl 0411.68039
[35] and , Integer Programming. Wiley, New York (1972).
[36] Gilbert, SIAM J. Appl. Math. 16 pp 1– (1968)
[37] Gomory, J. SIAM 9 pp 551– (1961)
[38] Hakimi, Networks 1 pp 113– (1971)
[39] Net wiring for large scale integrated circuits. IBM Res. Report RC 1375 (1965).
[40] Hanan, J. SIAM Appl. Math. 14 pp 255– (1966)
[41] Hanan, IEEE Trans. Circuit Theory CT-19 pp 74– (1972)
[42] Graph Theory. Addison-Wesley, Reading, MA (1969).
[43] Held, Math. Progr. 6 pp 62– (1974)
[44] Hwang, IEEE Trans. Reliability R30 pp 416– (1981)
[45] Hwang, SIAM J. Appl. Math. 30 pp 104– (1976)
[46] Hwang, J. Design Automation Fault Tolerance Anal. 2 pp 303– (1978)
[47] Hwang, J. ACM 26 pp 177– (1979)
[48] Hwang, IEEE Trans. Circuits Systems CAS-26 pp 75– (1979)
[49] Reducibility among combinatorial problems. In and (Eds.), Complexity of Computer Computations. Plenum Press, New York (1972) 85–103. · doi:10.1007/978-1-4684-2001-2_9
[50] An algorithm for transforming a spanning tree into a Steiner tree. Proc. 9th Int. Math. Progr. Symp., Budapest 1976. North-Holland, Amsterdam (1979) 349–357.
[51] Kou, Acta Informatica 15 pp 141– (1981)
[52] The generalized Steiner problem. Unpublished note (1978).
[53] Kruskal, Proc. Amer. Math. Soc. 7 pp 48– (1956)
[54] Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976).
[55] Lee, IEEE Trans. Circuits and Systems CAS-23 pp 470– (1976)
[56] Levin, Soviet Math. Dokl. 12 pp 1477– (1971)
[57] Magnanti, Transportation Sci. 18 pp 1– (1984)
[58] Martello, Networks 12 pp 89– (1982)
[59] Melzak, Canad. Math. Bull. 4 pp 143– (1961) · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[60] , and , Minimum-weight two-connected spanning networks. Unpublished paper. · Zbl 0689.90071
[61] Nastansky, Zeitsch. Operations Res. 18 pp 59– (1974)
[62] Plesnik, Math. Slovaca 31 pp 155– (1981)
[63] Prim, Bell System Tech. J. 36 pp 1389– (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x
[64] , and , Steiner’s problem on two-trees. Tech. Rep. RO 850315, Dept. de Math. Ecole Polytechnique Federale de Lausanne, Suisse (1985).
[65] Convexity and the Steiner tree problem. Tech. Report 85/3, Dept. of Operations Research and System Analysis, Univ. of North Carolina, Chapel Hill (1985).
[66] Rayward-Smith, Int. J. Math. Educ. Sci. Technol. 14 pp 15– (1983)
[67] and , On finding Steiner vertices. Tech. Rep., School of Comp. Studies and Accountancy, Univ. of East Anglia (1984).
[68] Richey, Networks 15 pp 217– (1985)
[69] Sahni, SIAM J. Comput. 3 pp 262– (1974)
[70] The node-weighted Steiner tree problem. Tech. Rep., School of Business Administration, Univ. of California, Berkeley, CA. (1985).
[71] Shore, Networks 12 pp 323– (1982)
[72] Smith, Networks 11 pp 23– (1981)
[73] Smith, Eng. Optimization 4 pp 179– (1980)
[74] Smith, Eng. Optimization 4 pp 15– (1979)
[75] Approximation algorithms for Steiner tree problems. Tech. Rep. 249, Dept. of Comp. Science, Yale Univ. (1982).
[76] Takahashi, Math. Japonica 24 pp 573– (1980)
[77] Valiant, SIAM J. Comput. 8 pp 410– (1979)
[78] and , Steiner trees in probabilistic networks. Tech. Rep. Nr. 82–7, Dept. of Comp. Science, Univ. of Saskatchewan (1982).
[79] Wald, Congr. Numerantium 36 pp 15– (1982)
[80] Wald, Networks 13 pp 159– (1983)
[81] White, Networks 15 pp 109– (1985)
[82] The Steiner problem. M.Sc. Thesis, Inst. of Datalogy Univ. of Copenhagen, Denmark (1981).
[83] Winter, Networks 15 pp 323– (1985)
[84] Winter, BIT 25 pp 485– (1985)
[85] Steiner problem in Halin networks. To appear in Discrete Applied Mathematics. · Zbl 0623.94024
[86] Winter, J. Algorithms.
[87] Generalized Steiner problem in Halin networks. In preparation. · Zbl 0623.94024
[88] Construction of minimum distance rectangle trees. In preparation.
[89] Wong, Math. Program. 28 pp 271– (1984)
[90] and , An algorithm for the wiring problem. Digest of the IEEE Int. Symp. on Electrical Networks. London (1971) 14–15.
[91] and , Optimal and suboptimal solution algorithms for the wiring problem. Proc. IEEE Int. Symp. Circuit Theory (1972) 154–158.
[92] Yang, IEEE Trans. Circuit Theory CT-19 pp 508– (1972)
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.