No label defined (Q4946041)

An all-optical network can be modeled as a graph \(G= (V,E)\) in which any edge \(xy\in E\) represents a pair of point-to-point unidirectional optical fiber links connecting a pair of nodes \(x\) and \(y\). A dipath \(p\) from \(x\) to \(y\) \((x,y\in V)\) is the unidirected path joining \(x\) to \(y\), in which each edge is considered traversed in the direction from \(x\) to \(y\). Given a graph \(G\) and a set \(P\) of dipaths on \(G\), the problem is to assign a color (wavelength) to each dipath in \(P\) in such a way that two dipaths that share a link must have different color assignments. This paper surveys theoretical results for wavelength-routing in all-optimal networks and presents several open problems. The authors highlight the most important graph-theoretic and algorithmic problems in this area and present some proofs of known results to illustrate the most effective techniques. Since the general problem is NP-hard, they focus on special cases of set \(P\), special structures of graph \(G\) and different modes of routing. For the entire collection see [Zbl 0933.00056].