Title :
Polynomial algorithm for min-cost delay-constrained multicasting routing problem in networks
Author :
Erzin, Adil I. ; Kim, Sang-Ha
Author_Institution :
Dept. of Comput. Sci., Chungnam Nat. Univ., Taejon, South Korea
Abstract :
We propose a novel polynomial algorithm for constructing a min-cost communication tree to connect the subset of network nodes which forms the multicast group of destinations in such way that the delays along each path from the source vertex to the sinks do not exceed the given delay bounds. From the mathematical point of view this is a Steiner tree problem with restrictions on the lengths of the paths from the root to destinations
Keywords :
approximation theory; computational complexity; delays; minimisation; polynomials; telecommunication network routing; trees (mathematics); Steiner tree problem; complexity; delay bounds; destinations; min-cost communication tree; min-cost delay-constrained multicasting; multicast group; network nodes; network routing; polynomial approximation algorithm; root; sinks; source vertex; Approximation algorithms; Bandwidth; Computer science; Costs; Delay; Intelligent networks; Multicast algorithms; Polynomials; Routing; Tree graphs;
Conference_Titel :
Information, Communications and Signal Processing, 1997. ICICS., Proceedings of 1997 International Conference on
Print_ISBN :
0-7803-3676-3
DOI :
10.1109/ICICS.1997.652307
