APproximation algorithms for constructing wavelength routing networks

摘要

Consider a requirement graph whose vertices represent customers and an edge represents the need to route a unit of flow between its end vertices along a single path. All these flows are to be routed simultaneously. A solu- Tion network consists of a (multi)graph on the same set Of vertices, such that it is possible to route simulta- Neously all of the required flows in such a way that no Edge is used more than K times. The SYNTHESIS of WAVE- LENGTH ROUTING NETWORK (SWRN) problem is to compute a Solution network of a minimum number of edges.