Isomorphisms of the De Bruijn digraph and free-space optical networks

David Coudert 1, * Afonso Ferreira 1 Stéphane Pérennes 1
* Auteur correspondant
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 : The de Bruijn digraph B(d, D) has degree d, diameter D, dD vertices, and dD+1 arcs. It is usually defined by words of size D on an alphabet of cardinality d, through a cyclic left-shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an arbitrary permutation on the alphabet and an arbitrary permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is cyclic. We use this result to improve from O(dD+1) to the number of lenses required for the implementation of B(d, D) by the Optical Transpose Interconnection System proposed by Marsden et al. [Opt Lett 18 (1993), 1083-1085].
Type de document :
Article dans une revue
Networks, Wiley, 2002, 40 (3), pp.155 - 164. <10.1002/net.10043>
Liste complète des métadonnées


https://hal.inria.fr/inria-00429201
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 19:37:38
Dernière modification le : dimanche 1 novembre 2009 - 21:57:46
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:57:41

Fichier

CFP-Networks-ac02.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Afonso Ferreira, Stéphane Pérennes. Isomorphisms of the De Bruijn digraph and free-space optical networks. Networks, Wiley, 2002, 40 (3), pp.155 - 164. <10.1002/net.10043>. <inria-00429201>

Partager

Métriques

Consultations de
la notice

231

Téléchargements du document

92