Routing and transmitting problems in de Bruijn networks
Zhen Liu, Ting‐Yi Sung · IEEE Transactions on Computers · 1996
De Bruijn graphs, both directed and undirected, have received considerable attention as architecture for interconnection networks. In this paper, we focus on undirected de Bruijn networks of radix d and dimension 0, denoted by UB(d, 0). We first discuss the shortest-path routing problem. We present properties of the shortest paths between any two vertices of UB(d, 0) and propose two shortest-path routing algorithms, one of which has linear time complexity. Secondly, we study the transmitting problem. We establish a lower bound for the optimal transmitting time which implies in particular that the optimal transmitting problem is trivial for UB(d, 0) when d/spl ges/5. We present a transmitting scheme on undirected binary de Bruijn networks UB(2, n) with transmitting time n-1 for n/spl ges/5, and conjecture that the optimal transmitting time is n-1 for UB(2, n), and n for U8(3, n) and UB(4, n).