Cycle Covering

Jean-Claude Bermond 1 Lilian Chacon 2 David Coudert 1 Francois Tillerot 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 Orange Labs [Lannion]
Abstract : 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.
Keywords : cycle covering WDM graph survivability
Type de document :
Communication dans un congrès
8th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Jun 2001, Vall de Nuria, Spain. Carleton Scientific, pp.21-34, 2001, Proceedings in Informatics
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00429183
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 16:03:25
Dernière modification le : lundi 23 avril 2018 - 10:52:05
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:55:36

Fichier

BCCT-SIROCCO01.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429183, version 1

Collections

UNICE | INRIA | I3S | TDS-MACS | UNIV-COTEDAZUR

Citation

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. Carleton Scientific, pp.21-34, 2001, Proceedings in Informatics. 〈inria-00429183〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

451

Téléchargements de fichiers

108

Contact


archive-ouverte@inria.fr