| 多播路由算法MPH的时间复杂度研究 |
| |
| 引用本文： | 蒋廷耀,李庆华. 多播路由算法MPH的时间复杂度研究[J]. 电子学报, 2004, 32(10): 1706-1708 |
| |
| 作者姓名： | 蒋廷耀 李庆华 |
| |
| 作者单位： | 1. 三峡大学电气信息学院,湖北宜昌 443002;2. 华中科技大学计算机学院,湖北武汉 430074 |
| |
| 摘 要： | 多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务,一个最小代价的多播路由算法是NP完全的,在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法,本文对该算法进行了理论分析和证明,并做了广泛的仿真实验,结果表明其时间复杂度是O(m2n)而不是过去文献中所给出的O(m2n+e).
|
| 关 键 词： | 多播路由 最小成本 时间复杂度 |
| 文章编号： | 0372-2112(2004)10-1706-03 |
| 收稿时间： | 2003-06-30 |
A Corrigendum to the Time Complexity of Multicast Routing Algorithm MPH |
| |
| JIANG Ting-yao ,,LI Qing-hua. A Corrigendum to the Time Complexity of Multicast Routing Algorithm MPH[J]. Acta Electronica Sinica, 2004, 32(10): 1706-1708 |
| |
| Authors: | JIANG Ting-yao LI Qing-hua |
| |
| Affiliation: | 1. College of Electrical Engineering and Information Technology,China Three Gorges University,Yichang,Hubei 443002,China;2. College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan,Hubei 430074,China |
| |
| Abstract: | 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. |
| |
| Keywords: | multicast routing minimum cost time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载免费的PDF全文 |
|
