几种特殊结构全光网中多播路由的波长分配算法
研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m+1)(log r/√m+1+1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.
作 者： 帅天平 Shuai Tianping 作者单位： 北京邮电大学理学院,北京,100876 刊 名： 系统科学与数学 ISTIC PKU 英文刊名： JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES 年，卷(期)： 2007 27(6) 分类号： O1 关键词： 多播请求 波长分配 近似算法 性能比