HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Sunday, November 1, 2009 - 4:03:25 PM
Last modification on : Friday, February 4, 2022 - 3:18:23 AM
Long-term archiving on: : Thursday, June 17, 2010 - 6:55:36 PM


Files produced by the author(s)


  • HAL Id : inria-00429183, version 1



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⟩



Record views


Files downloads