摘要
考虑多纤波分复用链网与环网中的利润极大化问题,分别给出了多项式时间精确算法和2-近似算法.对于环上各边光纤数目相同的均匀模式,给出了1.582-近似算法.这些结果也适用于有向链网与环网.
The problem of the total maximizing profits of accepted requests in multifiber WDM chain and ring networks is considered. A polynomial time exact algorithm to solve the problem for chains and a 2-approximation algorithm for rings are presented. The uniform variant in rings where all edges have the same number of fibers is also considered and a 1.582-approximation algorithm is presented. These results can also be adapted to the directed chains and rings.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2006年第5期7-11,共5页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目(60373025)
教育部科学技术研究重点项目
天津教委科技发展基金资助项目(20051519)
关键词
近似算法
多纤光网络
波分复用
路由
路染色
approximation algorithms
muhifiber optical networks
WDM
routing
path coloring
