An iterative algorithm for delay-constrained minimum-cost multicasting
作者： M. Parsa , Qing Zhu , J.J. Garcia-Luna-Aceves
DOI: 10.1109/90.720901
关键词:
摘要: The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost trees with delay constraints. BSMA can handle asymmetric link characteristics and variable bounds on destinations, specified as real values, minimizes the total cost of a routing tree. Instead single-pass tree construction approach used in most previous heuristics, new based feasible-search optimization strategy that starts minimum-delay monotonically decreases by iterative improvement delay-bounded BSMA's expected time complexity analyzed, simulation results are provided showing achieve near-optimal reduction fast execution.
core.ac.uk
acm.org
sci-hub.se 参考文章(24)
L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees Acta Informatica. ,vol. 15, pp. 141- 145 ,(1981) , 10.1007/BF00288961
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Jin Y. Yen, Finding the K Shortest Loopless Paths in a Network Management Science. ,vol. 17, pp. 712- 716 ,(1971) , 10.1287/MNSC.17.11.712
R. C. Prim, Shortest Connection Networks And Some Generalizations Bell System Technical Journal. ,vol. 36, pp. 1389- 1401 ,(1957) , 10.1002/J.1538-7305.1957.TB01515.X
R.K. Brayton, G.D. Hachtel, A.L. Sangiovanni-Vincentelli, A survey of optimization techniques for integrated-circuit design Proceedings of the IEEE. ,vol. 69, pp. 1334- 1362 ,(1981) , 10.1109/PROC.1981.12170
N. Katoh, T. Ibaraki, H. Mine, An efficient algorithm for K shortest simple paths Networks. ,vol. 12, pp. 411- 427 ,(1982) , 10.1002/NET.3230120406
V. J. Rayward‐Smith†, The computation of nearly minimal Steiner trees in graphs International Journal of Mathematical Education in Science and Technology. ,vol. 14, pp. 15- 23 ,(1983) , 10.1080/0020739830140103
Michael L. Fredman, Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms Journal of the ACM. ,vol. 34, pp. 596- 615 ,(1987) , 10.1145/28869.28874
B.M. Waxman, Routing of multipoint connections IEEE Journal on Selected Areas in Communications. ,vol. 6, pp. 1617- 1622 ,(1988) , 10.1109/49.12889
Eugene L. Lawler, Combinatorial optimization : networks and matroids Dover Publications. ,(1976)