Performance analysis of algorithms for the Steiner problem in directed networks. (English) Zbl 1075.05601
Liebling, T. (ed.) et al., Latin-American conference on combinatorics, graphs and applications. Papers from the conference, Santiago, Chile, August 16–20, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 18, 67-72 (2004).
For the entire collection see [Zbl 1074.05004].
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Berman, P.; Ramaiyer, V.: Improved appr. Algor. for the Steiner tree prob.. J. of algor. 17, 381-408 (1994) · Zbl 0820.68049 |
| [2] | H. Bravo, A. Candia and N. Maculan, The Steiner prob. in dir. acyclic graphs, Unpubl. paper, 1999 |
| [3] | A. Candia and H. Bravo-Azlán, Worst-case perform. of Wong’s Steiner tree heuristic, Discr. Appl. Math. (accepted) 2004 |
| [4] | Charikar, M.; Chekuri, Ch.; Cheung, T.; Dai, Z.; Goel, A.; Guha, S.; Li, M.: Appr. alg. For dir. Steiner prob.. J. of algor. 33, No. 1, 73-91 (1999) · Zbl 0937.68155 |
| [5] | Dahl, G.: Directed Steiner prob. With connectivity constraints. Discr. appl. Math. 47, 109-128 (1993) · Zbl 0789.68106 |
| [6] | Hwang, F.; Richards, D.; Winter, P.: The Steiner tree problem. (1992) · Zbl 0774.05001 |
| [7] | Karp, R.: Reducibility among combin. Prob.. Complex. of computer comp., 85-103 (1972) |
| [8] | Kou, L.; Markovsky, G.; Berman, L.: A fast alg. For Steiner trees. Acta inform. 15, 141-145 (1981) · Zbl 0445.68051 |
| [9] | Liu, W.: A lower bound for the Steiner tree problem in dir. Graphs. Networks 20, 765-778 (1990) · Zbl 0721.90076 |
| [10] | Maculan, N.: The Steiner prob. In graphs. Annals of discrete math. 31, 185-212 (1987) |
| [11] | O. Palma and N. Maculan, A heur. meth. for the Steiner prob. in dir. graphs, Proc. of Latin. Cong. on OR (III CLAIO), Santiago (1986)117 – 140 (In Portuguese) |
| [12] | Polzin, T.; Vahdati, S.: Improved alg. For the Steiner prob. In networks. Discr. appl. Math. 112, No. 1 – 3, 263-300 (2001) · Zbl 0994.90135 |
| [13] | Ramanathan, S.: Multic. tree gener. In networks with asymm. Links. IEEE INFOCOM/ACM trans. On networking 4, 558-568 (1996) |
| [14] | H.F. Salama, Eval. of multic. routing alg. for real-time comm. on high-speed networks, IFIP Sixth Int. Conf. on High Perf. Netw. (1995)27 – 42 |
| [15] | Takahashi; Matsuyama: An appr. Solution for the Steiner prob. In graphs. Math. japonica 24, 573-577 (1980) · Zbl 0435.05036 |
| [16] | Voss, S.: Worst-case perf. Of some heur. For Steiner prob. In directed graphs. Ipl 48, 99-105 (1993) · Zbl 0788.68111 |
| [17] | Winter, P.; Gregor-Smith, J. Mac: Path-distance heuristics for the Steiner prob. In undirec. Graphs. Algorithmica 7, 309-327 (1992) · Zbl 0748.05052 |
| [18] | Wong, R.: A dual ascent approach for Steiner prob. On a directed graph. Math prog. 28, 271-287 (1984) · Zbl 0532.90092 |
| [19] | Zelikovsky, A.: A series of appr. Alg. for the acyclic dir. Steiner tree prob.. Algorithmica 18, 99-110 (1997) · Zbl 0873.68079 |
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.
