×

Isomorphisms of the De Bruijn digraph and free-space optical networks. (English) Zbl 1064.68010

Summary: The de Bruijn digraph \(B(d, D)\) has degree \(d\), diameter \(D\), \(d^D\) vertices, and \(d^{D+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(d^{D+1})\) to \(\Theta(\sqrt{d^{D+1}})\) the number of lenses required for the implementation of \(B(d, D)\) by the Optical Transpose Interconnection System proposed by G. Marsden, P. Marchand, P. Harvey and S. Esener [Opt. Lett. 18, 1083–1085 (1993)].

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Graphes, Gauthier-Villars, Paris, 1983.
[2] Bermond, Discr Appl Math 84 pp 21– (1998)
[3] Bermond, Int J Fond Comput Sci 8 pp 109– (1997)
[4] and Optical transpose interconnection system for vertical emitters, OSA Topical Meeting on Optics in Computing, OSA, Lake Tahoe, NV, March 1997, pp. 233-235.
[5] Bridges, J Comb Theory Ser B 29 pp 339– (1980)
[6] Cao, Theoretical Comp Sci 222 pp 113– (1999)
[7] Chiarulli, IEEE/OSA J Light Tech 14 pp 1601– (1996)
[8] Collins, J ACM 39 pp 931– (1992)
[9] Algorithmique et optimisation de réseaux de communications optiques, Ph.D. Thesis, Université de Nice Sophia-Antipolis, December 2001.
[10] Coudert, IEEE/OSA J Light Tech 18 pp 2076– (2000)
[11] Coudert, OSA Appl Opt 39 pp 2965– (2000)
[12] Communications dans les réseaux de processeurs, Collection ERI, Masson, Paris, 1994.
[13] Feldman, OSA Appl Opt 27 pp 1742– (1988)
[14] Imase, IEEE Trans Comput 30 pp 439– (1981)
[15] Imase, IEEE Trans Comput 32 pp 782– (1983)
[16] Bounds on directed (d, k) graphs. Theory of cellular logic networks and machines, AFCRL-68-0668, SRI Project 7258, Final report, 1968, pp. 20-28.
[17] Marsden, OSA Opt Lett 18 pp 1083– (1993)
[18] Optical communication networks, Series on Computer Communications, McGraw-Hill, New York, 1997.
[19] and Directed graphs with minimal diameter and maximal connectivity, Technical report, Oakland University, School of Engineering, 1980.
[20] and A class of graphs for processor interconnection, Int Conf Parallel Processing, and (Editors), IEEE Computer Society Press, New York, NY, 1983, pp. 154-157.
[21] Communications dans les architectures à mémoire distribuée, Ph.D. Thesis, Université de Nice Sophia-Antipolis, 1992.
[22] and ?Energy requirement and speed analysis of electrical and free-space optical digital interconnections,? Optical interconnections and parallel processing: Trends at the interface, and (Editors), Kluwer, Boston, 1997, pp. 49-128.
[23] Zane, J Parallel Distr Comput 60 pp 521– (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.