计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2011年
5期
53-55
,共3页
哈林网络%Steiner树%线性算法
哈林網絡%Steiner樹%線性算法
합림망락%Steiner수%선성산법
设计一个在哈林网络中求解Steiner树的线性时间算法,提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举,递归压缩哈林图中的扇,通过还原所有扇得到Steiner树.算法的正确性证明、复杂度分析及应用实例分析证明,该算法对于哈林网络的多播选路具有重要的参考价值.
設計一箇在哈林網絡中求解Steiner樹的線性時間算法,提齣偽扇的概唸併在偽扇擴充至扇的過程中對Steiner樹在扇中可能齣現的狀態進行枚舉,遞歸壓縮哈林圖中的扇,通過還原所有扇得到Steiner樹.算法的正確性證明、複雜度分析及應用實例分析證明,該算法對于哈林網絡的多播選路具有重要的參攷價值.
설계일개재합림망락중구해Steiner수적선성시간산법,제출위선적개념병재위선확충지선적과정중대Steiner수재선중가능출현적상태진행매거,체귀압축합림도중적선,통과환원소유선득도Steiner수.산법적정학성증명、복잡도분석급응용실례분석증명,해산법대우합림망락적다파선로구유중요적삼고개치.