基于MPH的时延约束Steiner树算法

作     者：周灵 孙亚民 Zhou Ling;Sun Yamin

作者机构：南京理工大学计算机科学与技术学院 

基　　金：国家教育部博士点专项基金项目(20050288015) 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2008年第45卷第5期

页      码：810-816页

摘      要：为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.

主 题 词：组播路由 Steiner树 MPH算法 时延约束 NP-complete 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203224895...