一种基于松弛算法改进的最小组播树生成方法

作     者：向雄 李羡童 XIANG Xiong;LI Mu-tong

作者机构：广州大学华软软件学院网络技术系 

基　　金：广东省普通高校特色创新项目(No.2016KTSCX188) 广州大学华软软件学院教学、科学研究项目(No.ky201613) 广州大学华软软件学院信息管理与信息系统特色专业建设(No.ZDZY201701) 

出 版 物：《现代计算机》 (Modern Computer)

年 卷 期：2019年第25卷第27期

页      码：9-15页

摘      要：最小组播树是一个经典的网络传输问题。组播树生成问题可泛化为斯坦纳树问题,但后者通常情况下是一个NP完全问题。目前已经存在很多包括松弛算法在内的近似算法用于组播树的生成,但没有一种能达到最优。分析松弛算法执行过程中的所形成的环路,发现其中有些环路是可优化的,优化之后即可降低整棵树的传播低价,于是提出一种通过破除可优化环来生成最小组播树的方法。该方法首先分析可优化环的条件,分析环路中的中转节点的特点,设计寻找环的分支节点的子算法和破环的子算法,最终得出寻找最小代价组播树的方法,数据模拟结果表明,在不增加时间复杂度的前提下该方法能够获得目前为止最小的组播树代价。

主 题 词：组播 斯坦纳树 最短路径 松弛算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1007-1423.2019.27.002

馆 藏 号：203817966...