Cycle Covering - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2001

Cycle Covering

Résumé

This paper considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other. We focus on the case where the optical WDM network is a ring, there are requests between any pair of vertices and the covering is done with small cycles. This problem can be modelled as follows: Find a covering of the edges of a logical graph I (here the complete graph Kn ) by subgraphs Ik of a certain kind (here cycles Ck of length k), such that, for each Ik , there exists in the physical graph G (here Cn ) a disjoint routing of the edges of Ik . The aim is to minimize the number of subgraphs Ik in the covering. We give optimal solutions for that problem.
Fichier principal
Vignette du fichier
BCCT-SIROCCO01.pdf (147.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00429183 , version 1 (01-11-2009)

Identifiants

  • HAL Id : inria-00429183 , version 1

Citer

Jean-Claude Bermond, Lilian Chacon, David Coudert, Francois Tillerot. Cycle Covering. 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Jun 2001, Vall de Nuria, Spain. pp.21-34. ⟨inria-00429183⟩
204 Consultations
75 Téléchargements

Partager

Gmail Facebook X LinkedIn More