On DRC-covering of Kn by cycles

Jean-Claude Bermond 1 David Coudert 1 Min-Li Yu 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
Abstract : This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF-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 Kn, where V(Kn) = 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 Kn 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 = Cn, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4.
Type de document :
Article dans une revue
Journal of Combinatorial Designs, Wiley, 2003, 11 (2), pp.100 - 112. <10.1002/jcd.10040>
Liste complète des métadonnées

https://hal.inria.fr/inria-00429205
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 19:48:22
Dernière modification le : dimanche 1 novembre 2009 - 21:58:34
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:57:47

Fichier

BCY-JCD03.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Claude Bermond, David Coudert, Min-Li Yu. On DRC-covering of Kn by cycles. Journal of Combinatorial Designs, Wiley, 2003, 11 (2), pp.100 - 112. <10.1002/jcd.10040>. <inria-00429205>

Partager

Métriques

Consultations de
la notice

187

Téléchargements du document

104