论文部分内容阅读
我们考虑的问题来自于基于波分复用技术(WDM)的全光环形网络,给定环形网络中一个路(通讯请求)的集合,将每一条路分配一个波长,使得经过相同连接的路必须分配不同的波长,我们的目标就是找一个波长分配方案使所需的波长数目最小,令ω表示为路集中最大两两相交路的个数,本文我们设计了一个可以保证指派到路集的波长数目不超过1.5ω的近似算法,因为ω是路集所需波长最小数目的一个下界,所以该算法的近似比不超过1.5。
The problem we consider comes from the all-optical ring network based on wavelength division multiplexing (WDM). Given a set of paths (communication requests) in a ring network, each path is assigned a wavelength such that the path through the same connection must Assigning different wavelengths, our goal is to find a wavelength distribution scheme that minimizes the number of wavelengths required, so that ω represents the maximum number of two or more intersections in a road set. In this paper, we design a wavelength that assures the assigned road set Approximate number of not more than 1.5ω algorithm, because ω is the minimum number of wavelengths required for the road set a lower bound, so the approximate ratio of the algorithm does not exceed 1.5.