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).
Type de document :
Rapport
[Research Report] RR-1130, INRIA. 1990, pp.20
Liste complète des métadonnées

https://hal.inria.fr/inria-00075429
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:11:48
Dernière modification le : samedi 27 janvier 2018 - 01:31:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 23:07:38

Fichiers

Identifiants

  • HAL Id : inria-00075429, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

102

Téléchargements de fichiers

78