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

On DRC-Covering of K_n by Cycles

Jean-Claude Bermond 1 David Coudert 1 Min-Li Yu 1
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 work considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on sub-networks which are protected independently from each other. The problem can be stated as follows: for a given graph $G$, find a cycle covering of the edge set of $K_n$, where $V(K_n) = V(G)$, such that each cycle in the covering satisfies the disjoint routing constraint (DRC), relatively to $G$, which can be stated as follows : to each edge of $K_n$ we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where $G = C_n$, a ring of size $n$ and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem and as well as for variations of the problem, namely, its directed version and the case when cycle length is fixed as 4.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:18:54 PM
Last modification on : Friday, February 4, 2022 - 3:12:36 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:02:14 PM


  • HAL Id : inria-00072288, version 1



Jean-Claude Bermond, David Coudert, Min-Li Yu. On DRC-Covering of K_n by Cycles. [Research Report] RR-4299, INRIA. 2001. ⟨inria-00072288⟩



Record views


Files downloads