Bottleneck multicast trees in linear time

On a directed graph with arc costs and a given source node, s, we consider the problem of computing multicast (Steiner) trees spanning any given node subset, V, so that the maximum of the tree arc costs is minimized. We show that this problem can be solved by simply solving the bottleneck path problem, i.e., the problem of determining for each node, t/spl ne/s, a path from s to t so that the maximum of path arc costs is minimized. For the latter problem we provide an implementation of Dijkstra's algorithm that runs in linear time under mild assumptions on arc costs.