# Approximable 1-Turn Routing Problems in All-Optical Mesh Networks

1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In all-optical networks, several communications can be transmitted through the same fiber link provided that they use different wavelengths. The MINIMUM ALL-OPTICAL ROUTING problem (given a list of pairs of nodes standing for as many point to point communication requests, assign to each request a route along with a wavelength so as to minimize the overall number of assigned wavelengths) has been paid a lot of attention and is known to be np-hard. Rings, trees and meshes have thus been investigated as specific networks, but leading to just as many np-hard problems. This paper investigates 1-turn routings in meshes (paths are allowed one turn only). We first show the MINIMUM LOAD 1-TURN ROUTING problem to be np-hard but 2-apx (more generally, the MINIMUM LOAD $k$-CHOICES ROUTING problem is np-hard but k-apx), then that the MINIMUM 1-TURN PATHS COLOURING problem is 4-apx (more generally, any d-segmentable routing of load L in a hypermesh of dimension d can be coloured with 2d(L-1)+1 colours at most). From there, we prove the MINIMUM ALL-OPTICAL 1-TURN ROUTING problem to be apx.
Document type :
Journal articles

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371891
Contributor : Jérôme Palaysi <>
Submitted on : Monday, March 30, 2009 - 4:46:36 PM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM

### Identifiers

• HAL Id : lirmm-00371891, version 1

### Citation

Jérôme Palaysi, Guillaume Bagan, Olivier Cogis. Approximable 1-Turn Routing Problems in All-Optical Mesh Networks. Algorithmic Operations Research, Preeminent Academic Facets, 2009, 4 (2), pp.095-101. ⟨lirmm-00371891⟩

Record views