Fault-tolerant routings in large generalized cycles

A generalized p-cycle is a digraph whose set of vertices is partitioned into p parts that can be ordered in such a way that a vertex is adjacent only to vertices in the next part. The families of BGC(p,d,d ^k) (de Bruijn Generalized Cycles) and KGC(p,d,d^p+k+d^k) (Kautz Generalized Cycles) are the largest known p-cyles for their degree and diameter. In this paper, we present routing algorithms for both families. Such algorithms route over paths of length at most the value of the diameter plus two units. Moreover, this bound is attained only in the case that the number of faulty elements (nodes or links) is maximum