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

David Coudert 1, * Afonso Ferreira 1 Stéphane Pérennes 1
* Corresponding author
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 : 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].
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00429201
Contributor : David Coudert <>
Submitted on : Sunday, November 1, 2009 - 7:37:38 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on : Thursday, June 17, 2010 - 6:57:41 PM

File

CFP-Networks-ac02.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

333

Files downloads

188