系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2007年
6期
837-846
,共10页
多播请求%波长分配%近似算法%性能比
多播請求%波長分配%近似算法%性能比
다파청구%파장분배%근사산법%성능비
研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m+1)(log r/√m+1+1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.
研究全光WDM網絡中多播請求的路由與波長分配問題.給定網絡拓撲和一組多播通信請求,要求對其進行路由和波長分配,滿足波長連續性和波長無遲突約束,使得所用的波長總數最少.就幾類特殊網絡進行瞭研究.首先對二分樹網絡進行瞭研究,此時問題是多項式時間可求解的.其次對樹網絡進行瞭討論,證明瞭即使是星網絡,問題也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,這裏m是星圖的邊數.隨後給齣瞭近似比為(√m+1)(log r/√m+1+1)的近似算法,此結果對一般圖也成立.最後攷慮瞭環網和樹環網,給齣瞭近似比為3.6和2△的近似算法,這裏△是圖的最大度.
연구전광WDM망락중다파청구적로유여파장분배문제.급정망락탁복화일조다파통신청구,요구대기진행로유화파장분배,만족파장련속성화파장무충돌약속,사득소용적파장총수최소.취궤류특수망락진행료연구.수선대이분수망락진행료연구,차시문제시다항식시간가구해적.기차대수망락진행료토론,증명료즉사시성망락,문제야불존재근사비소우m1/2-ρ(0＜ρ＜1))적근사산법,제비NP=ZPP,저리m시성도적변수.수후급출료근사비위(√m+1)(log r/√m+1+1)적근사산법,차결과대일반도야성립.최후고필료배망화수배망,급출료근사비위3.6화2△적근사산법,저리△시도적최대도.
