×

Steiner tree problems. (English) Zbl 0749.90082

Summary: We give a survey up to 1989 on the Steiner tree problems which include the four important cases of Euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We also provide a rather comprehensive and up-to-date bibliography which covers more than three hundred items.

MSC:

90C35 Programming involving graphs or networks
05C05 Trees
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, Networks 20 pp 453– (1990)
[2] Aho, Networks 7 pp 37– (1977)
[3] Aneja, Networks 10 pp 167– (1980)
[4] , and , Problems easy for tree-decomposable graphs. Automata Languages and Programming [LNCS 317] ( and , Eds.) Springer-Verlag, Berlin (1988) 38–51.
[5] , and , Le Probleme de Steiner sur un Graphe Oriente: Formulations and Relaxations. Publication 315. Centre de Recherche sur les Transports, University of Montreal (1983).
[6] An Atlas of Steiner Networks. Monograph 9. Institute of Math. Geography, Ann Arbor, MI (1989).
[7] Ausiello, J. Comput. Syst. Sci. 33 pp 179– (1986)
[8] Formulations and algorithms for the Steiner network problem. Unpublished manuscript, Sloan School Management, MIT (1982).
[9] Balakrishnan, Networks 17 pp 65– (1987)
[10] Balas, Operations Res. Lett. 7 pp 279– (1988)
[11] Beardwood, Proc. Cambr. Philos. Soc. 55 pp 299– (1959)
[12] Beasley, Networks 14 pp 147– (1984)
[13] Beasley, Networks 19 pp 1– (1989)
[14] A heuristic for the Euclidean and rectilinear Steiner problems. Working Paper, Management School, Imperial College, London (1989).
[15] Network design problems: Steiner trees and spanning k-trees. PhD Dissertation, Computer Science Division, University of California at Berkeley (1987).
[16] Two probabilistic results on rectilinear Steiner trees. Algorithmica (1988) 191–204. · Zbl 0648.90080
[17] Bern, Networks 20 pp 109– (1990)
[18] and , Further polynomially solvable special cases of the Steiner problem in planar graphs. Preprint (1989).
[19] and , A greedy heuristic for the rectilinear Steiner tree problem. Technical Report, Computer Science Division, University of California at Berkeley (1985).
[20] and , The shortest-network problem. Sci. Am. January (1989) 84–89.
[21] Bern, Info. Process. Lett. 32 pp 171– (1989)
[22] Bharath-Kumar, IEEE Trans. Commun. COM-31 pp 343– (1983)
[23] Optimal design of gas pipeline networks. PhD Dissertation, University of Adelaide, Australia (1978).
[24] Bhaskaran, J. Operational Res. Soc. 30 pp 1047– (1979)
[25] Bienstock, SIAM J. Comput. 17 pp 53– (1988)
[26] Bienstock, Networks 19 pp 79– (1989)
[27] Bienstock, Algorithmica
[28] Dynamic programming on graphs with bounded treewidth. Automata, Languages and Programming [LNCS 317] ( and , Ed.). Springer-Verlag (1988) 103–118.
[29] NC-algorithms for graphs with small treewidth. Graph-Theoretic Concepts in Computer Science [LNCS 344]. (Ed.). Springer-Verlag, Berlin (1988) 1–10.
[30] Booth, Disc. Comput. Geom.
[31] Booth, Ann. Oper. Res.
[32] , and , Recursively constructed graphs: decomposition and linear-time algorithm generation. Preprint (1989).
[33] and , STEINER72: An improved version of the minimal network problem. Technical Report 35, Comp. Sci. Res. Ctr., Bell Labs (1975).
[34] Boyce, ACM Trans. Math. Software 3 pp 339– (1977)
[35] Camin, Evolution 19 pp 311– (1965)
[36] Cavalli-Sforza, Am. J. Hum. Genet. 19 pp 233– (1967)
[37] Cedergren, Crit. Rev. Biochem. 11 pp 35– (1981)
[38] Chang, J. ACM 19 pp 699– (1972)
[39] The design of network configurations with linear or piecewise linear cost functions. Symp. Comput. Commun., Networks, Teletraffic (1972) 363–369.
[40] New algorithm for Steiner tree on graphs. IEEE Symp Circuits Syst. (1983) 1217–1219.
[41] Cheung, SIAM J. Appl. Math. 34 pp 225– (1978)
[42] , and , A powerful global router: Based on Steiner min-max trees. Preprint (1989).
[43] Chung, Math. Mag. 62 pp 83– (1989)
[44] Chung, Bull. Inst. Math. Acad. Sinica 4 pp 313– (1976)
[45] Chung, Ann. Disc. Math. 2 pp 173– (1978)
[46] Chung, Geometriae Dedicata 11 pp 353– (1981)
[47] Chung, Ann. N.Y. Acad. Sci. 440 pp 328– (1985)
[48] , and , Dynamic search in graphs. Discrete Algorithms and Complexity ( et al., Eds.). Academic, New York (1987) 351–387. · doi:10.1016/B978-0-12-386870-1.50026-5
[49] Chung, SIAM J. Appl. Math. 34 pp 27– (1978)
[50] Chung, Networks 9 pp 19– (1979)
[51] Clark, Phys. Ed. 16 pp 32– (1981)
[52] and , Une nouvelle formulation du probleme de Steiner sur un graphe. Publication 280, Centre de Recherche sur les Transports, University of Montreal (1983).
[53] Cockayne, Can. J. Math. 10 pp 431– (1967) · Zbl 0161.19203 · doi:10.4153/CMB-1967-041-8
[54] Cockayne, SIAM J. Appl. Math. 18 pp 150– (1970)
[55] Cockayne, Info. Proc. Lett. 22 pp 151– (1986)
[56] Cockayne, Algorithmica
[57] and , Improved computation of plane Steiner minimal trees. Preprint (1989).
[58] Cockayne, Q. Appl. Math. 26 pp 213– (1967)
[59] Cockayne, Math. Mag. 42 pp 206– (1969)
[60] Cockayne, Congressus Numeratium (Proc. 14th S. E. Conf. on Combinatorics, Graph Theory and Computing) 39 pp 203– (1983)
[61] and , Computation of a Steiner minimal tree. Combinatorics ( and , Eds.). Inst. Math. Appl. (1972) 53–71.
[62] Cohoon, IEEE Trans. Comput.-Aided Design 9 pp 398– (1990)
[63] Colbourn, Discrete Math. 86 pp 179– (1990)
[64] , and , The graphical travelling salesman problem and some related integer polyhedra. Research Report 378, Appliquees de Grenoble (1983).
[65] and , What Is Mathematics? Oxford University Press, New York (1941). · Zbl 0060.12302
[66] Culberson, Info. Proc. Lett. 30 pp 215– (1989)
[67] D’Atri, SIAM J. Comput. 17 pp 521– (1988)
[68] , and , The Steiner tree problem and homogeneous sets. Math. Foundations Comput. Sci. [LNCS 324] (1988) 249–261.
[69] Day, J. Theor. Biol. 103 pp 429– (1983)
[70] Day, Bull. Math. Biol. 49 pp 461– (1987) · Zbl 0623.92018 · doi:10.1007/BF02458863
[71] Day, Syst. Zool. 35 pp 224– (1986)
[72] Day, Math. Biosci. 81 pp 33– (1986)
[73] Day, J. Theor. Biol. 124 pp 213– (1987)
[74] Dreyfus, Networks 1 pp 195– (1972)
[75] , and , Minimal length trees on the unit sphere. Preprint (1989).
[76] Dror, INFOR 28 pp 266– (1990)
[77] Du, Ann. Oper. Res.
[78] Du, Trans. Am. Math. Soc. 278 pp 137– (1983)
[79] Du, Networks 16 pp 47– (1986)
[80] Du, Acta Math. Appl. Sinica 3 pp 246– (1987)
[81] Du, Proc. Am. Math. Soc. 95 pp 613– (1985)
[82] Du, Disc. Comput. Geom. 2 pp 401– (1987)
[83] Du, Trans. Am. Math. Soc. 278 pp 149– (1983)
[84] Du, Disc. Comput. Geom. 2 pp 65– (1987)
[85] Du, J. Combinatorial Theory Ser. A 38 pp 230– (1985)
[86] Du, J. Combinatorial Theory Ser. A 32 pp 396– (1982)
[87] Duin, Networks 17 pp 353– (1987)
[88] Duin, Operations Res. Lett. 8 pp 79– (1989)
[89] Duin, Eur. J. Operational Res. 39 pp 332– (1989)
[90] Duin, Networks 19 pp 549– (1989)
[91] Duin, Ann. Oper. Res.
[92] El-Arbi, RAIRO (Operations Res.) 12 pp 207– (1978)
[93] Erickson, Math. Operations Res. 12 pp 634– (1987)
[94] Farley, SIAM J. Alg. Disc. Methods 1 pp 70– (1980)
[95] Farris, Syst. Zool. 19 pp 83– (1970)
[96] Felsenstein, Q. Rev. Biol. 57 pp 379– (1982)
[97] Felsenstein, Annu. Rev. Genet. 22 pp 521– (1988)
[98] Few, Mathematika 2 pp 141– (1955)
[99] Fitch, Syst. Zool. 20 pp 406– (1971)
[100] Fitch, Am. Naturalist 111 pp 223– (1977)
[101] Foulds, Optima 10 pp 1– (1983)
[102] Foulds, J. Theor. Biol. 107 pp 471– (1984)
[103] Foulds, Discrete Appl. Math. 15 pp 271– (1986)
[104] and , A branch and bound approach to the Steiner problem in graphs. Proceedings of the 14th Annual Conference of the Operational Research Society of New Zealand (1978), Vol. 1, 61–70.
[105] Foulds, J. Combin. Inf. Syst. Sci. 6 pp 215– (1981)
[106] Foulds, Adv. Appl. Math. 3 pp 43– (1982)
[107] Foulds, Eng. Optimization 7 pp 7– (1983)
[108] Friedel, SIAM J Appl. Math. 49 pp 960– (1989)
[109] Application of linear graph theory to printed circuits. Proc. Asilomar Conf. Syst. Circuits (1967) 721–728.
[110] Gallawa, Fiber Integrated Opt. 1 pp 289– (1978)
[111] Mathematical games. Sci. Am. June (1986) 16–22.
[112] Garey, SIAM J. Appl. Math. 32 pp 835– (1977)
[113] Garey, SIAM J. Appl. Math. 32 pp 826– (1977)
[114] and , Computers and Intractability. W. H. Freeman, San Francisco (1979).
[115] Georgakopoulos, J Algorithms 8 pp 122– (1987)
[116] Gilbert, J. SIAM 13 pp 376– (1965)
[117] Gilbert, Bell Syst. Tech. J. 46 pp 2209– (1967) · doi:10.1002/j.1538-7305.1967.tb04250.x
[118] Gilbert, SIAM J. Appl. Math. 16 pp 1– (1968)
[119] and , On the parsimonious property of connectivity problems. Working Paper, Sloan School, MIT (1989).
[120] Graham, Math. Biosci. 60 pp 133– (1982)
[121] Graham, Bull. Inst. Math. Acad. Sinica 4 pp 177– (1976)
[122] Gray, Nucleic Acids Res. 12 pp 5837– (1984)
[123] Hakimi, Networks 1 pp 113– (1971)
[124] and , Parallel heuristics for the Steiner tree problem in images without sorting or routing. Technical Report 89-048, Computer Science Dept., Purdue University (1989).
[125] Net wiring for large scale integrated circuits. RC 1375. IBM Research Report (1965).
[126] Hanan, J. SIAM Appl. Math. 14 pp 255– (1966)
[127] Hanan, IEEE Trans. Circuit Theory CT-19 pp 74– (1972)
[128] Harigan, Biometrics 29 pp 53– (1973)
[129] Hendy, Math. Biosci. 59 pp 277– (1982)
[130] Hendrickson, Math. Biosci. 3 pp 371– (1968)
[131] , and , Optimization of Steiner trees using genetic algorithms. Proceedings of the Third International Conference on Genetic Algorithms (1989) 231–236.
[132] , and , A new approach to the rectilinear Steiner tree problem, Proceedings of the 26th Design Automation Conference (1989) 161–166.
[133] , and , Constructing the optimal rectilinear Steiner tree derived from a minimum spanning tree. Digest of Tech. Papers ICCAD-89 (1989) 6–9.
[134] Theoretical model to optimal drainage. To appear.
[135] , and , A path selection global router. 24th ACM/IEEE Design Automation Conference (1987) 641–644.
[136] Hwang, SIAM J. Appl. Math. 30 pp 104– (1976)
[137] Hwang, Design Automation Fault Tolerant Comput. 3 pp 303– (1978)
[138] Hwang, IEEE Trans. Circuits Syst. CAS-26 pp 75– (1979)
[139] Hwang, J. ACM 26 pp 177– (1979)
[140] Hwang, Operations Res. Lett. 5 pp 235– (1986)
[141] Hwang, Math. Mag.
[142] Hwang, Disc. Comput. Geom. 3 pp 367– (1988)
[143] Hwang, Disc. Math. 62 pp 49– (1986)
[144] and , Shortest networks with a given topology. Preprint.
[145] Hwang, Disc. Math. 45 pp 107– (1983)
[146] Hwang, Algorithmica 5 pp 591– (1990)
[147] Some notes on the Steiner tree problem in graphs. Optimization of Connection Structures in Graphs (A. Iwainsky, Ed.). Centr. Inst. of Cyb. a. Inform. Processes, Berlin (1985) 57–73.
[148] Iwainsky, Networks 16 pp 205– (1986)
[149] and , Some variants of a heuristic approach to the solution of the Steiner tree problem in graphs, to appear.
[150] Jain, Networks 19 pp 793– (1989)
[151] The Steiner problem on directed graphs: A probabilistic analysis of the duality gap. Preprint (1989).
[152] Jarnik, Casopis Pesk. Mat. Fyr. 63 pp 223– (1934)
[153] Jiang, J. Fudan Univ. (Natural Sci.) 25 pp 343– (1986)
[154] Johnson, J. Algorithms 6 pp 434– (1985)
[155] Johnson, J. Algorithms 8 pp 438– (1987)
[156] An empirical study of exact algorithms for the cardinality Steiner problem. Master’s Thesis, Simon Fraser University, Burnaby, B.C. Canada (1987).
[157] An Artificial Intelligence Approach to VLSI Routing. Kluwer Academic, Boston (1986).
[158] Kallman, Stud. Appl. Math. 22 pp 141– (1973) · Zbl 0258.50003 · doi:10.1002/sapm1973522141
[159] Reducibility among combinatorial problems. Complexity of Computer Computations. ( and , Ed.). Plenum Press, New York (1972) 85–103. · doi:10.1007/978-1-4684-2001-2_9
[160] The probabilistic analysis of some combinatorial search algorithms. Algorithms and Complexity: New Directions and Recent Results. (Ed.). Academic Press, New York (1976) 1–19.
[161] Karp, Math. Operations Res. 2 pp 209– (1977)
[162] Katz, Eur. J. Operational Res. 6 pp 166– (1981)
[163] Komlos, Networks 15 pp 413– (1985)
[164] An algorithm for transforming a spanning tree into a Steiner tree. Survey of Math Programming (Proc 9th Int. Math. Prog. Symp.), Vol. 2, North-Holland, Amsterdam (1979) 349–357.
[165] Optimálne spojovacie systemy (in Czech). Mathematické Metódy v. Hospodársky Praxi (Ed.). Vydavatelstvo Slovenskej Akadémie Vied, Bratislava (1961).
[166] Kou, Acta Info. 27 pp 369– (1990)
[167] Kou, Congressus Numerantium 59 pp 147– (1987)
[168] Kou, Acta Info. 15 pp 141– (1981)
[169] , , and , Near optimal algorithms for finding minimum Steiner trees on random graphs. Mathematical Foundations of Computer Science 1986 [LNCS 233] ( et al., Eds.). Springer-Verlag, Berlin (1986) 501–511.
[170] Steiner’s problem revisited. Studies in Optimization, Vol. 10 ( and , Eds.). Math Association of America, Wash. D.C. (1975) 98–107.
[171] Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976).
[172] Lee, Networks 6 pp 351– (1976)
[173] Lee, SIAM J. Comput. 9 pp 200– (1980)
[174] Some industrial case studies of Steiner trees. Preprint (1989).
[175] Lee, IEEE Trans. Circuits Syst. CAS-23 pp 470– (1976)
[176] and , A new global router for row-based layout. IEEE Int. Conf. Computer-Aided Design (1988) 180–183.
[177] The shortest connection of a group of graph vertices [in Russian]. Proc. of the Inst. of Math., Voronez State University (1970) 6–17.
[178] Levin, Soviet Math. Doklady 12 pp 1477– (1971)
[179] Construction of Steiner trees with obstacles in the plane. Masters Thesis, Dept. Computer Science, University of Illinois (1978).
[180] Luna, Discrete Appl. Math. 18 pp 199– (1987)
[181] Lundy, Biometrika 72 pp 191– (1985)
[182] Lundy, Math. Prog. 34 pp 111– (1986)
[183] Ma, Chin. J. Comput. 8 pp 237– (1985)
[184] , and , Branch-and-bound as a higher-order function. Preprint (1989).
[185] O problema de Steiner em grafos orientados. II Congresso Latino-americano de Pesquina Operacional e Engenharia de Sistemas, Buenos Aires (1984) 206–213.
[186] Maculan, Ann. Discrete Math. 31 pp 185– (1987)
[187] and , An approach for the Steiner problem in directed graphs. Preprint (1989).
[188] Rectilinear arborescence and rectilinear Steiner tree problems. PhD Dissertation, University of Birmingham (1980).
[189] Megiddo, Networks 8 pp 1– (1978)
[190] Mehlhorn, Info. Process. Lett. 27 pp 125– (1988)
[191] Melzak, Can. Math. Bull. 4 pp 143– (1961) · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[192] Companion to Concrete Mathematics. Wiley, New York (1973).
[193] and , Polyconics 1: Polyellipses and optimization. Q. J. Math. (1977) 239–255. · Zbl 0367.50010
[194] Miehle, Oper. Res. 6 pp 232– (1958)
[195] Minoux, INFOR 28 pp 221– (1990)
[196] Moore, J. Theor. Biol. 38 pp 459– (1973)
[197] Moran, J. Combinatorial Theory Ser. B 37 pp 113– (1984)
[198] Nastansky, Z. Operations Res. 18 pp 59– (1974)
[199] , and , A language for describing rectilinear Steiner tree configurations. 23rd ACM/IEEE Design Automation Conference (1986) 659–662.
[200] Ollerenshaw, Inst. Math. Appl. 15 pp 208– (1978)
[201] Palermo, IBM J. Res. Dev. 5 pp 335– (1961)
[202] Contribuicao para a Resolucao do Problema de Steiner num Grafo Direcionado: un Metodo Heuristico. PhD Dissertation, Systems Engineering Computer Science, COPPE, Federal University of Rio de Janeiro (1985).
[203] Penny, CABIOS 3 pp 183– (1987)
[204] Plesnik, Math. Slovaca 31 pp 155– (1981)
[205] On heuristics for the Steiner problem in graphs. Preprint (1989).
[206] Pollak, J. Combinatorial Theory, Ser. A 24 pp 278– (1978)
[207] Induction and Analogy in Mathematics. Princeton University Press, Princeton, NJ (1954).
[208] , and , Steiner’s problem on two-trees. Technical Report RO850315, Ecole Polytechnique Federale de Lausanne (1985).
[209] A polynomial algorithm for the Steiner tree problem on terminal-planar graphs. Technical Report UNC/ORSA/Tech. Rep.-83/10, Dept. Operations Research, University of North Carolina, Chapel Hill (1983).
[210] Provan, Networks 18 pp 55– (1988)
[211] Provan, SIAM J Comput. 17 pp 920– (1988)
[212] Provan, Ann. Oper. Res.
[213] Provan, Operations Res. 32 pp 516– (1984)
[214] and , A min-max equation for Steiner trees on rectangular grids. Preprint (1989).
[215] Rao, Algorithmica
[216] , and , A polynomial algorithm for a class of Steiner tree problems on graphs. Indus. and Syst. Engr. Rep. Series J-82-5, Georgia Institute of Technology (1982).
[217] Rayward-Smith, Int. J. Math. Ed. Sci. Technol. 14 pp 15– (1983)
[218] Rayward-Smith, Networks 16 pp 283– (1986)
[219] Richards, Algorithmica 4 pp 191– (1989)
[220] Richards, Ann. Oper. Res.
[221] Richards, Algorithmica
[222] Rogers, Syst. Zool. 33 pp 52– (1984)
[223] Rohlf, Syst. Zool. 33 pp 341– (1984)
[224] Rubenstein, Ann. Oper. Res.
[225] and , A variational approach to the Steiner ratio conjecture for six points. J. Combinatorial Theory Ser. A.
[226] and , Critical points for the Steiner ratio conjecture. Preprint (1989).
[227] Rudowski, Arch. Autom. Telemech. 29 pp 353– (1984)
[228] Algorithms for solving the directed minimal Steiner tree problem. PhD Dissertation, University of Massachusetts, Amherst (1981).
[229] Sankoff, SIAM J. Appl. Math. 28 pp 35– (1975)
[230] and , Simultaneous comparison of three or more sequences related by a tree. Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. ( and , Eds.). Addison-Wesley, Reading, MA (1983) 253–263.
[231] Sankoff, J. Mol. Evol. 7 pp 133– (1976)
[232] Sankoff, Nucleic Acids Res. 10 pp 421– (1982)
[233] Sankoff, Math. Program. 9 pp 240– (1975)
[234] and , Geometric Steiner min-max trees. Preprint (1989).
[235] Segev, Networks 17 pp 1– (1987)
[236] Servit, Digital Processes 7 pp 21– (1981)
[237] and , Closest-point problems. 16th Annual Symp. on Foundations of Computer Science (1975) 151–162.
[238] Shore, Networks 12 pp 323– (1982)
[239] Generalized Steiner network problems. PhD Dissertation, University of Illinois, Urbana (1978).
[240] Steiner minimal trees with obstacles. Technical Report, Dept. Indust. Engr. and Oper. Res., University of Massachusetts (1982).
[241] Generalized Steiner network problems in engineering design. Engineering Design (Ed.). Academic Press, New York (1985) 119–161.
[242] Smith, J. Socio. Econ. Planning 16 pp 21– (1982)
[243] Smith, Eng. Optimization 4 pp 179– (1980)
[244] Smith, Networks 11 pp 23– (1981)
[245] Smith, Eng. Optimization 4 pp 15– (1979)
[246] Smith, Appl. Math. Modelling 4 pp 369– (1980)
[247] Smith, Ann. Oper. Res.
[248] Studies in computational geometry motivated by mesh generation. PhD dissertation, Princeton University (1988).
[249] Smith, Algorithmica
[250] On minimal rectilinear Steiner trees in all dimensions. Proc. 6th ACM Symp. Comput. Geom. (1990) 311–320.
[251] Soukup, SIAM J. Appl. Math. 29 pp 571– (1975)
[252] Soukup, ACM/SIGMAP Newsletter 22 pp 37– (1977)
[253] Soukup, SIGMAP Newsletter 15 pp 48– (1973)
[254] Am. math. mon. problem. Preprint.
[255] Steele, Ann. Probability 9 pp 365– (1982)
[256] Mathematical Snapshots. Oxford University Press, New York (1960).
[257] Approximation algorithms for Steiner tree problems. Technical Report 249, Dept. Computer Science, Yale University (1982).
[258] Algorithms for minimal trees and semi-Steiner trees based on the simplex method (Abstract). Proc. Princeton Symp on Math Program. (1970) 614–615.
[259] Suzuki, Asia-Pacific J. Operations Res. 3 pp 106– (1986)
[260] Takahashi, Math. Jpn. 24 pp 573– (1980)
[261] Takamizawa, J. ACM 29 pp 623– (1982)
[262] and , Trassierung und Plazierung auf Graphenmodellen. Vortrags-Sammelband der 4. Fachtagung Numerische Realisierung Math. Modelle (1981) 215–231.
[263] and , New heuristic algorithms for solving the Steiner tree problem in graphs. To appear.
[264] (a.k.a. Thompson), , and , Computing a rectilinear Steiner minimal tree in no(n) time. Parallel Algorithms and Architectures [LNCS 269] ( et al., Eds.). Akademie-Verlag, Berlin, 1987, 176–183. · doi:10.1007/3-540-18099-0_44
[265] Thompson, Ann. Hum. Genet. Lond. 36 pp 333– (1973)
[266] Tideman, IBM J. Res. Dev. 6 pp 259– (1962)
[267] Trietsch, SIAM J. Appl. Math. 45 pp 855– (1985)
[268] Trietsch, SIAM J. Appl. Math. 50 pp 244– (1990)
[269] Trietsch, Networks 15 pp 365– (1983)
[270] Trubin, Cybernetics 21 pp 320– (1985)
[271] van de Heyden, Int. Ser. Numer. Math. 36 pp 79– (1977)
[272] and , Global wiring for custom layout design. Proc. Intl. Symp. Circuits and Systems (1985) 207–208.
[273] Degree-constrained Steiner problem. Proc. EuroVIII (1986).
[274] A survey of some generalizations of Steiner’s problem in graphs. Proc. First Balkan Conf. Operations Res. (1988).
[275] Steiner’s problem in directed graphs: Logical tests in a branch and bound algorithm. Preprint (1989).
[276] Voss, Methods Operations Res. 58 pp 239– (1989)
[277] Voss, Methods Operations Res. 57 pp 161– (1987)
[278] A linear algorithm for a class of problems on partial 2-trees. Manuscript, Schlumberger Tech. Corp. (1987).
[279] and , Steiner trees in outerplanar graphs. Proc. 13th S.E. Conf. Combinatorics, Graph Theory, and Computing (1982) 15–22.
[280] Wald, Networks 13 pp 159– (1983)
[281] Wald, Microelectron. Reliab. 23 pp 837– (1983)
[282] Wald, ACM Trans. Database Sys. 9 pp 348– (1984)
[283] A multiple source algorithm for suboptimum Steiner trees in graphs. Proc WG’85 (1985) 387–396.
[284] and , A new routing algorithm and its hardware implementation. Proc. 23rd ACM/IEEE Design Automation Conf. (1986) 574–580.
[285] Waxman, IEEE J. Selected Areas Comm. 6 pp 1617– (1988)
[286] Probable performance of Steiner tree algorithms. Technical report WUCS-88-4, Dept. Computer Science, Washington University, St. Louis (1988).
[287] Waxman, Info. Proc. Lett. 29 pp 283– (1988)
[288] Weng, Acta Math. Appl. Sinica 8 pp 129– (1983)
[289] Weng, Acta Math. Appl. Sinica 8 pp 383– (1985)
[290] Werner, Can. Geographer 13 pp 47– (1969)
[291] White, Networks 15 pp 109– (1985)
[292] Fast approximation algorithms for Steiner’s problem in graphs. Technical report, Inst. fur Angew. Info., University of Karlsruhe (1985).
[293] On approximation algorithms for Steiner’s problem in graphs. Graph-Theoretic Concepts in Computer Science [LNCS 246] ( and , Eds.). Springer-Verlag, Berlin (1986) 17–28.
[294] The Steiner problem. M.Sc. Thesis, Inst. of Datalogy, University of Copenhagen, Denmark (1981).
[295] Winter, Networks 15 pp 323– (1985)
[296] Winter, BIT 25 pp 485– (1985)
[297] Winter, J. Algorithms 7 pp 549– (1986)
[298] Winter, Networks 17 pp 129– (1987)
[299] Winter, Discrete Appl. Math. 17 pp 281– (1987)
[300] Generalized Steiner problem in Halin networks. To appear. · Zbl 0623.94024
[301] Construction of minimum distance rectangle trees. To appear.
[302] Wong, Math. Programming 28 pp 271– (1984)
[303] Wu, Acta Info. 23 pp 223– (1986)
[304] Algorithms for global routing. 23rd ACM/IEEE Design Automation Conference (1986) 824–830.
[305] and , An algorithm for the wiring problem. Digest IEEE Int. Symp. Electrical Networks (1971) 14–15.
[306] Yang, IEEE Trans. Circuit Theory CT-19 pp 508– (1972)
[307] and , Optimal and suboptimal solution algorithms for the wiring problem. Proc. IEEE Int. Symp. Circuit Theory (1972) 154–158.
[308] Yang, IEEE Trans. Circuit Theory CT-20 pp 250– (1973) · doi:10.1109/TCT.1973.1083680
[309] and , The Steiner ratio conjecture for six points. Tienjing Conf. Combinatorial Optimization (1988).
[310] Werner, Papers of Regional Sci. Assoc. pp 173– (1968)
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.