摘要
本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 。
In this paper,we consider the scheduling and wavelength assignment(SWA) problem which arises in optical wavelengthdivisionmultiplexing(WDM) networks.We only study the nonpreemptive case.If the number of wavelengths (processors) is a fixed constant,we prove that the SWA problem is NPhard and present a polynomial time approximation scheme (PTAS) to solve it.If the number of processors isn't fixed,we prove that there does not exist an approximation scheme for the problem.
出处
《应用数学》
CSCD
北大核心
2004年第1期67-72,共6页
Mathematica Applicata
基金
SupportedbytheNationalNaturalScienceFoundationofChina (1 0 2 71 0 6 5 )
