All-to-All Routing and Coloring in Weighted Trees of Rings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1999

All-to-All Routing and Coloring in Weighted Trees of Rings

Stéphane Pérennes
  • Fonction : Auteur
  • PersonId : 942945
David Tóth
  • Fonction : Auteur

Résumé

A tree of rings is an undirected graph obtained from the union of rings, which intersect two by two in at most one node, such that any two nodes are connected by exactly two edge-disjoint paths. In this paper, we consider symmetric directed trees of rings with weighted nodes. A routing for a weighted digraph is a collection of directed paths (dipaths), such that for each ordered pair of nodes (x_1,x_2) with respective weights w_1 and w_2, there are w_1w_2 dipaths (possibly not distinct) from x_1 to x_2. Motivated by the Wavelength Division Multiplexing (WDM) technology in all-optical networks, we study the problem of finding a routing which can be colored by the fewest number of colors so that dipaths of the same color are arc-disjo- int. We prove that this minimum number of colors (wavelengths) is equal to the maximum number of dipaths that share one arc (load), minimized over all routings. The problem can be efficiently solved (dipaths found and colored) using cut properties.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3700.pdf (250.53 Ko) Télécharger le fichier

Dates et versions

inria-00072968 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072968 , version 1

Citer

Bruno Beauquier, Stéphane Pérennes, David Tóth. All-to-All Routing and Coloring in Weighted Trees of Rings. RR-3700, INRIA. 1999. ⟨inria-00072968⟩
108 Consultations
225 Téléchargements

Partager

Gmail Facebook X LinkedIn More