| 改进的时延约束Steiner树算法 |
| |
| 引用本文： | 徐剑,倪宏,邓浩江,刘磊.改进的时延约束Steiner树算法[J].西安交通大学学报,2013,47(8). |
| |
| 作者姓名： | 徐剑 倪宏 邓浩江 刘磊 |
| |
| 作者单位： | 1. 中国科学院大学,100049,北京;中国科学院声学研究所国家网络新媒体工程技术研究中心,100190,北京
2. 中国科学院声学研究所国家网络新媒体工程技术研究中心,100190,北京 |
| |
| 基金项目： | 国家高技术研究发展计划资助项目，国家科技支撑计划资助项目，中国科学院战略性先导科技专项子课题 |
| |
| 摘 要： | 针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法.该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树.理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价.
|
| 关 键 词： | Steiner树 代价 时延约束 路径递增 链路共享 |
An Advanced Algorithm for Delay-Constrained Steiner Tree |
| |
| XU Jian
,
NI Hong
,
DENG Haojiang
,
LIU Lei.An Advanced Algorithm for Delay-Constrained Steiner Tree[J].Journal of Xi'an Jiaotong University,2013,47(8). |
| |
| Authors: | XU Jian NI Hong DENG Haojiang LIU Lei |
| |
| Abstract: | |
| |
| Keywords: | Steiner tree cost delay-constrained path increasing link sharing |
| 本文献已被 万方数据 等数据库收录！ |
|
