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.
Key words:
Halin network,
Steiner tree,
linear algorithm
摘要： 设计一个在哈林网络中求解Steiner树的线性时间算法，提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举，递归压缩哈林图中的扇，通过还原所有扇得到Steiner树。算法的正确性证明、复杂度分析及应用实例分析证明，该算法对于哈林网络的多播选路具有重要的参考价值。
关键词:
哈林网络,
Steiner树,
线性算法
CLC Number:
LIU Yun-Ting. Linear Time Algorithm of Steiner Tree Problem in Halin Network[J]. Computer Engineering, 2011, 37(5): 53-55.
陆芸婷. 哈林网络中Steiner树问题的线性时间算法[J]. 计算机工程, 2011, 37(5): 53-55.