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

摘要：

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

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

所属期刊栏目：37

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2011-05-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：53-55