Approximable Row-Column Routing Problems in All-Optical Mesh Networks (revisited)

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 row-column routings in meshes (paths are allowed one turn only). We first show the MINIMUM LOAD ROW-COLUMN 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 ROW-COLUMN 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 ROW-COLUMN ROUTING problem to be APX.
Type de document :
Rapport
[Research Report] RR-07012, LIRMM. 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00150160
Contributeur : Jérôme Palaysi <>
Soumis le : lundi 11 juin 2007 - 10:46:12
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:04:02

Fichier

Identifiants

  • HAL Id : lirmm-00150160, version 2

Collections

Citation

Jérôme Palaysi, Olivier Cogis, Guillaume Bagan. Approximable Row-Column Routing Problems in All-Optical Mesh Networks (revisited). [Research Report] RR-07012, LIRMM. 2007. 〈lirmm-00150160v2〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

82