多播路由算法MPH的时间复杂度研究

蒋廷耀; 李庆华

您当前的位置：

首页 >

文章列表页 >

多播路由算法MPH的时间复杂度研究

论文 | 更新时间：2025-07-16

- 多播路由算法MPH的时间复杂度研究
- A Corrigendum to the Time Complexity of Multicast Routing Algorithm MPH
- 电子学报 2004年32卷第10期页码：1706-1708
- 作者机构：
  
  1. 三峡大学电气信息学院,湖北,宜昌,443002
  2. 华中科技大学计算机学院,湖北,武汉,430074
  3. 三峡大学电气信息学院湖北宜昌,443002
  4. 华中科技大学计算机学院湖北武汉,430074
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.60273075)
- DOI：
  中图分类号： TP393
- 纸质出版：2004
- 稿件说明：
移动端阅览
蒋廷耀, 李庆华. 多播路由算法MPH的时间复杂度研究[J]. 电子学报, 2004,32(10):1706-1708.

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.
蒋廷耀, 李庆华. 多播路由算法MPH的时间复杂度研究[J]. 电子学报, 2004,32(10):1706-1708. DOI：

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. DOI：

摘要

多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务

一个最小代价的多播路由算法是NP完全的

在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法

本文对该算法进行了理论分析和证明

并做了广泛的仿真实验

结果表明其时间复杂度是

O(m

而不是过去文献中所给出的

O(m

n+e)

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(nm

+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(nm

)

is proposed.

关键词

Keywords

references

浏览量

1053

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

低轨巨星座多品类业务流低复杂度分段路由方法

基于动态图的PPI网络构建和复合物挖掘算法研究

动态QoS多播路由协议

稀疏表示下的非监督显著对象提取

网络灵敏度的拓扑分析和算法的时间复杂度