The delay-constrained minimum spanning tree problem

We formulate the problem of constructing broadcast trees for real-time traffic with delay constraints in networks with asymmetric link loads as a delay-constrained minimum spanning tree (DCMST) problem in directed networks. Then, we prove that this problem is NP-complete, and we propose an efficient heuristic to solve the problem based on Prim´s algorithm for the unconstrained minimum spanning tree problem. Simulation results under realistic networking conditions show that our heuristic performance is close to optimal. Delay-constrained minimum Steiner tree heuristics can be used to solve the DCMST problem. Simulation results indicate that the fastest delay-constrained minimum Steiner tree heuristic, DMCT is not as efficient as the heuristic we propose, while the most efficient delay-constrained minimum Steiner tree heuristic, BSMA, is much slower than our proposed heuristic and does not construct delay-constrained broadcast trees of lower cost