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 <>
Submitted on : Sunday, November 1, 2009 - 4:03:25 PM
Last modification on : Tuesday, November 17, 2020 - 11:18:04 PM
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