Optimal routing in the de Bruijn networks

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, is considered. The distance functions for both the undirected and directed de Bruijn graphs are provided. The optimal routing problem is then reduced to that of pattern matching. Morris and Pratt´s (1970) failure function and Weiner´s (1973) prefix tree are used to develop algorithms that find the shortest paths in the unidirectional and bidirectional de Bruijn networks, respectively. These algorithms are linear in time and space (in the diameter of the graph). When approximately implemented, these linear algorithms have constant factors low enough to make them of practical use