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

AbstractIn 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⩽r⩽N−1, where N is the order of the considered graph). An unranking algorithm takes as input an integer r (0⩽r⩽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(D2), where D is the length of node labels