| 哈林网络中Steiner树问题的线性时间算法 |
| |
| 引用本文： | 陆芸婷. 哈林网络中Steiner树问题的线性时间算法[J]. 计算机工程, 2011, 37(5): 53-55 |
| |
| 作者姓名： | 陆芸婷 |
| |
| 作者单位： | 深圳信息职业技术学院信息技术研究所,广东深圳,518029 |
| |
| 基金项目： | 国家自然科学基金，广东省自然科学基金，深圳市科技计划基金 |
| |
| 摘 要： | 设计一个在哈林网络中求解Steiner树的线性时间算法，提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举，递归压缩哈林图中的扇，通过还原所有扇得到Steiner树。算法的正确性证明、复杂度分析及应用实例分析证明，该算法对于哈林网络的多播选路具有重要的参考价值。
|
| 关 键 词： | 哈林网络 Steiner树 线性算法 |
Linear Time Algorithm of Steiner Tree Problem in Halin Network |
| |
| LU Yun-ting. Linear Time Algorithm of Steiner Tree Problem in Halin Network[J]. Computer Engineering, 2011, 37(5): 53-55 |
| |
| Authors: | LU Yun-ting |
| |
| Affiliation: | LU Yun-ting(Institute of Information Technology,Shenzhen Institute of InformationTechnology,Shenzhen 518029,China) |
| |
| Abstract: | This paper presents a linear time algorithm to find the Steiner tree in Halin network.The algorithm proposes the concept of pseudo-fan.It enumerates all the possible conditions of Steiner tree in a fan during the expansion from pseudo-fan to fan and recursively shrinks fan structure.Steiner tree is found by reverting all the fans in the end.The proof of correctness and the analysis of the complexity of the algorithm are given.An example is presented.The algorithm has great value to the multicast routing in Halin network. |
| |
| Keywords: | Halin network Steiner tree linear algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
