A new routing algorithm for cyclic shifts on BRGC hypercubes (Q1318732)

We discuss routing algorithms for cyclic shifts on Binary-Reflected Gray Code (BRGC) hypercubes. The BRGC hypercube has the property that any two adjacent numbers are mapped to neighboring nodes that can communicate directly through a link. Therefore, when the shift distance is one, it uses only one link to route a message from any node to its sink node. However, all of the existing routing algorithms have their drawbacks. For example, some routing algorithms are not link-disjoint so that two routing paths will contend for the same link. The best link-disjoint routing algorithm in the literature uses at most \({4\over 3} n\) links between a pair of source-sink nodes on an \(n\)-dimensional BRGC hypercube. In this paper, we propose a new routing algorithm for cyclic shifts based on the divide-and-conquer approach. It uses at most \(n\) links to route a message from any node to its cyclic shifted sink node on an \(n\)- dimensional BRGC hypercube. Furthermore, this algorithm is link-disjoint such that each link is used at most once in all routing paths. Therefore, it is superior to any other routing algorithms for cyclic shifts on BRGC hypercubes.