WDM网络中的排序与波长分配问题的一个多项式时间近似方案(英文)  

A PTAS for the Scheduling and Wavelength Assignment Problem in WDM Networks

作　　者：张少强[1] 李国君[1] 

机构地区：[1]山东大学数学与系统科学学院,山东济南250100

出　　处：《应用数学》2004年第1期67-72,共6页Mathematica Applicata

基　　金：SupportedbytheNationalNaturalScienceFoundationofChina (1 0 2 71 0 6 5 )

摘　　要：本文考虑基于波分复用技术 (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.

关 键 词：WDM网络 波分复用技术 波长分配 多项式时间近似 无线通信 

分 类 号：TN92[电子电信—通信与信息系统] O224[电子电信—信息与通信工程]