Proof of optimal algorithm for maximum-bandwidth ALM tree construction
Takamichi Kikkawa, Takamichi Miyata, K. Yamaoka · 2009
We construct an ALM (application layer multicast) tree that achieves the maximum bandwidth by using underlay traffic information. Since this problem was previously shown to be NP-hard, no polynomial-time algorithms for maximum-bandwidth ALM tree construction exist. In our work, we assume that the underlay network has a tree network topology, and we show a polynomial-time algorithm that constructs a maximum-bandwidth ALM tree on such a tree network topology. We propose an ALM tree construction algorithm that achieves bandwidth b and apply this algorithm with various bandwidth values b. We show that it can make a maximum-bandwidth ALM tree in polynomial time.