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

Author

Wei, David S L ; Muga, Felix P., II ; Naik, Kshirasagar

Author_Institution

Dept. of Comput. & Inf. Sci., Fordham Univ., New York, NY, USA

Volume

10

Issue

12

fYear

1999

fDate

12/1/1999 12:00:00 AM

Firstpage

1290

Lastpage

1298

Abstract

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 Parallel and Distributed Systems is indeed isomorphic to the wrapped butterfly. The isomorphism was first reported by Muga and Wei in the proceedings of PDPTA ´96. The isomorphism is shown by using an edge-preserving bijective mapping. Due to the isomorphism, algorithms for the degree four Cayley graph can be easily developed in terms of wrapped butterfly and topological properties of one network can be easily derived in terms of the other. Next, we present the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in time O(√N), where N is the network size

Keywords

computational complexity; graph theory; multiprocessor interconnection networks; parallel algorithms; degree four Cayley graph; edge-preserving bijective mapping; optimal permutation routing algorithm; topological properties; wrapped butterfly; Algorithm design and analysis; Availability; Hypercubes; Multiprocessor interconnection networks; Routing;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.819950

Filename

819950