Optimization Online


Routing and wavelength assignment by partition coloring

Thiago Noronha (tfn***at***inf.puc-rio.br)
Celso Ribeiro (celso***at***inf.puc-rio.br)

Abstract: We show in this work how the problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition coloring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition coloring problem, which may be viewed as an extension of the graph coloring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition coloring by approximately 20% and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem.

Keywords: Routing, wavelength assignment, optical networks, partition coloring, tabu search

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, November 2003.

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/05/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society