Optimal Routing Algorithms for Generalized de Bruijn Digraphs

Generalized de Bruijn digraph, G_{B}(d,n), was proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to include any number of nodes. Du and Hwang showed that G_{B}(d, n) essentially retains all the nice properties of de Bruijn digraphs, and presented a leftlceil {log _d n} rightrceil -step routing algorithm, where d is the indegree and outdegree, and n is the number of nodes in the graph.