改进的时延约束Steiner树算法

• 作者: 倪宏 刘磊 徐剑 邓浩江
• 来源期刊: 西安交通大学学报
• 关键词: Steiner树 代价 时延约束 路径递增 链路共享
• 年，卷（期）: 2013,（8）
• 页码范围: 38-43
• 页数: 6页
• 分类号: TP393
• 语种: 中文
• DOI: 10.7652/xjtuxb201308007

摘要

针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法.该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树.理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	倪宏	中国科学院声学研究所国家网络新媒体工程技术研究中心	122	525	9.0	16.0
2	邓浩江	中国科学院声学研究所国家网络新媒体工程技术研究中心	66	613	9.0	23.0
3	刘磊	中国科学院声学研究所国家网络新媒体工程技术研究中心	181	1653	22.0	30.0
4	徐剑		9	76	6.0	8.0