Routing and transmitting problems in de Bruijn networks

Zhen Liu, Ting‐Yi SungIEEE Trans. Computers 1996 · DOI

Abstract

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).
BibTeX
@article{liu1996routing,
  author = {Zhen Liu and Ting‐Yi Sung},
  title = {{Routing and transmitting problems in de Bruijn networks}},
  journal = {IEEE Transactions on Computers},
  year = {1996},
  doi = {10.1109/12.537129},
}

Loading related content...

Figure