In many models of optical routing, a set of communication paths (req uests) in a network are given, and a wavelength must be assigned to each path so that paths sharing an edge receive different wavelengths. The goal is to assign as few wavelengths as possible, in order to make as efficient use as possible of the optical bandwidth. Much work in the area has considered the use of wavelen gth converters: if a node of a network contains a converter, any path passing th rough this node may change its wavelength. Having converters at some of the nodes can reduce the number of wavelengths down to congestion bound. Thus Wilfong and Winkler defined a set S of nodes to be sufficient if, placing converters at the nodes in S, every set of paths can be routed with a number of wavelengths equal to its congestion bound. In this paper, the minimum sufficient set problem in bi-directed networks is studied. The problem is transformed into minimum vertex cover problem and some algorithms are developed for the problem.%在许多光学路由中,对于给定一组通讯路的集合,必须对有公共边的路安排相同的波长.为了充分利用光学的带宽,目的是安排尽量少的波长数.但有时候也考虑使用波长转换器. 如果一个顶点安装转换器,任何经过这个顶点的路都可以改变其波长.因此在某些顶点安装波长转换器后可以将波长的数目减少到一个拥塞界,因此,Wilfong和Winkler定义了一个顶点集 S,在S上安装转换器后,任何路集都可以分配数目等于拥塞界的波长,这样的集合S被称为充分集.研究在双向网络中的最小充分集问题,并把他转化为最小顶点覆盖问题.对此问题给出几个算法.
展开▼
