论文部分内容阅读
在许多光学路由中,对于给定一组通讯路的集合,必须对有公共边的路安排相同的波长.为了充分利用光学的带宽,目的是安排尽量少的波长数.但有时候也考虑使用波长转换器.如果一个顶点安装转换器,任何经过这个顶点的路都可以改变其波长.因此在某些顶点安装波长转换器后可以将波长的数目减少到一个拥塞界,因此,Wilfong和Winkler定义了一个顶点集S,在S上安装转换器后,任何路集都可以分配数目等于拥塞界的波长,这样的集合S被称为充分集.研究在双向网络中的最小充分集问题,并把他转化为最小顶点覆盖问题.对此问题给出几个算法.
In many optical routes, for a given set of sets of communication paths, the same wavelengths must be arranged for paths with common edges. To take full advantage of the optical bandwidth, the goal is to arrange as few wavelengths as possible, but sometimes it is also contemplated Wavelength Converters. If a vertex mounts a converter, any path past this vertex can change its wavelength, so installing a wavelength converter at some vertices reduces the number of wavelengths to a congested boundary, so Wilfong and Winkler After a vertex set S is installed on S, any set of paths can be assigned a number equal to the wavelength of the congested bounds, so that the set S is called a sufficient set. To study the minimal sufficient set problem in bidirectional networks, He transforms to the minimum vertex coverage problem. Several algorithms are given for this problem.