Optimal Routing Algorithms for Generalized de Bruijn Digraphs
- 1 August 1993
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 167-174
- https://doi.org/10.1109/icpp.1993.130
Abstract
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 \left\lceil {\log _d n} \right\rceil -step routing algorithm, where d is the indegree and outdegree, and n is the number of nodes in the graph.Keywords
This publication has 6 references indexed in Scilit:
- Depth-first search approach for fault-tolerant routing in hypercube multicomputersIEEE Transactions on Parallel and Distributed Systems, 1990
- Generalized de Bruijn digraphsNetworks, 1988
- Connectivity of Regular Directed Graphs with Small DiametersIEEE Transactions on Computers, 1985
- A Design for Directed Graphs with Minimum DiameterIEEE Transactions on Computers, 1983
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- On the impossibility of Directed Moore GraphsJournal of Combinatorial Theory, Series B, 1980