论文部分内容阅读
我们考虑的问题来自于基于波分复用技术(WDM)的全光环形网络.给定环形网络中一个路(通讯请求)的集合,将每一条路分配一个波长,使得经过相同连接的路必须分配不同的波长.我们的目标就是找一个波长分配方案使所需的波长数目最小.令ω表示为路集中最大两两相交路的个数.本文我们设计了一个可以保证指派到路集的波长数目不超过1.5ω的近似算法.因为ω是路集所需波长最小数目的一个下界,所以该算法的近似比不超过1.5.