Efficient reconfiguration algorithms of de Bruijn and Kautz networks into linear arrays

In this paper, we prove the existence of ranking and unranking algorithms on d-ary de Bruijn and Kautz graphs. A ranking algorithm takes as input the label of a node and returns the rank r of that node in a hamiltonian path (0 less than or equal to r less than or equal to N - 1, where N is the order of the considered graph). An unranking algorithm takes as input an integer r (0 less than or equal to r less than or equal to N - 1) and returns the label of the rth ranked node in a hamiltonian path. Our results generalize results given by Annexstein for binary de Bruijn graphs. The key of our framework is based on a recursive construction of hamiltonian paths in de Bruijn and Kautz graphs. The construction uses suitable uniform homomorphisms of de Bruijn and Kautz graphs of diameter D on de Bruijn graphs of diameter D - 1. Our ranking and unranking algorithms have sequential time complexity in O(D-2), where D is the length of node labels. (C) 2001 Elsevier Science B.V. All rights reserved.