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

Optimal routing in the De Bruijn networks

Abstract : In this paper, we consider the problem of optimal routing in an interconnection network, called the De Bruijn network, where the sites are linked in the form of a De Bruijn graph. We provide the distance functions for the undirected as well as the directed De Bruijn graphs. The optimal routing problem is then reduced to that of pattern matching. We use Morris and Pratt's failure function and Weiner's prefix tree to develop algorithms that find the shortest paths in the uni-directional and in the bi-directional De Bruijn networks, respectively. These algorithms are linear in time and in space (in the diameter of the graph).
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:11:48 PM
Last modification on : Friday, February 4, 2022 - 3:16:13 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 11:07:38 PM


  • HAL Id : inria-00075429, version 1



Zhen Liu. Optimal routing in the De Bruijn networks. [Research Report] RR-1130, INRIA. 1990, pp.20. ⟨inria-00075429⟩



Record views


Files downloads