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

更新时间：2025-07-16

- A Corrigendum to the Time Complexity of Multicast Routing Algorithm MPH
- Acta Electronica Sinica Vol. 32, Issue 10, Pages: 1706-1708(2004)
- 作者机构：
  
  1. 三峡大学电气信息学院,湖北,宜昌,443002
  2. 华中科技大学计算机学院,湖北,武汉,430074
  3. 三峡大学电气信息学院湖北宜昌,443002
  4. 华中科技大学计算机学院湖北武汉,430074
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Published：2004
- 稿件说明：
移动端阅览
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：

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

Views

1053

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation

Research on PPI Network Construction and Complex Mining Algorithm Based on Dynamic Graph

A Dynamic QoS Multicast Routing Protocol

Unsupervised Salient Object Extraction Based on Sparse Representation

Topological Analysis of Network Sensitivity and Time Complexity of Algorithm

Related Author

LIU Huan

WANG Ning-yuan

LIU Liang

CHEN Dong

HAO Shi-guang

MIN Hui

LUO Ai-jing

LI Peng

Related Institution

Peng Cheng Laboratory

Beijing Institute of Space Mechanics & Electricity

Institute of Telecommunication and Navigation Satellites， China Academy of Space Technology

School of Informatics, Hunan University of Chinese Medicine

Key Laboratory of Medical Information Research （CSU）, College of Hunan Province

⁰