A Corrigendum to the Time Complexity of Multicast Routing Algorithm MPH
Tingyao Jiang · Dianzi xuebao · 2004
Multicasting is a communication service that allows a source to efficiently transmit copies of data packet to a set of destination nodes.The run time of multicast routing algorithm is a key problem in real time applications since finding a minimum cost multicast tree is NP-completeness.MPH(Minimum Path Cost Heuristic)algorithm is a famous heuristic solution to multicast routing.In this paper,we show that the O(nm2+e) time complexity of MPH in previous literatures is not correct by theory analysis and extensive simulation,where n is number of network nodes,m is number of destination nodes and e is number of network edges.Furthermore,a precise time bound O(nm2) is proposed.