Polynomial algorithm for min-cost delay-constrained multicasting routing problem in networks

摘要

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.