Isomorphism of degree four Cayley graph and wrapped butterfly and their optimal permutation routing algorithm

In this paper, we first show that the degree four Cayley graph proposed in a paper appearing In the January 1996 issue of IEEE Transactions on Paralle l and Distributed Systems is indeed isomorphic to the wrapped butterfly. Th e isomorphism was first reported by Muga and Wei in the proceedings of PDPT A " 96. The isomorphism is shown by using an edge-preserving bijective mapp ing. Due to the isomorphism, algorithms for the degree four Cayley graph ca n be easily developed in terms of wrapped butterfly and topological propert ies of one network can be easily derived in terms of the other. Next, we pr esent the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in ti me O(root N), where N is the network size.