scientific article; zbMATH DE number 1421019

From MaRDI portal
Publication:4946041





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].




Cited in
(24)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4946041)