哈林网络中Steiner树问题的线性时间算法  

Linear Time Algorithm of Steiner Tree Problem in Halin Network

作　　者：陆芸婷[1] 

机构地区：[1]深圳信息职业技术学院信息技术研究所,广东深圳518029

出　　处：《计算机工程》2011年第5期53-55,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60672150);广东省自然科学基金资助项目(7008733);深圳市科技计划基金资助项目(SY200806300270A)

摘　　要：设计一个在哈林网络中求解Steiner树的线性时间算法,提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举,递归压缩哈林图中的扇,通过还原所有扇得到Steiner树。算法的正确性证明、复杂度分析及应用实例分析证明,该算法对于哈林网络的多播选路具有重要的参考价值。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.

关 键 词：哈林网络 STEINER树 线性算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]