Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.419-427 (May 1999)
Uni-directional Alternating Group Graphs

Jung-Sing Jwo and Tai-Ching Tuan*
Department of Computer and Information Sciences
Tunghai University
Taichung, Taiwan 407, R.O.C.
*ITESS, ASSET Group
Science Applications International Corporation
McLean, Virginia 22102, U.S.A.

A class of uni-directional Cayley graphs based on alternating groups is proposed in this paper. It is shown that this class of graphs is strongly connected and recursively scalable. The analysis of the shortest distance between any pair of nodes in a graph of this class is also given. Based on the analysis, we develop a polynomial time routing algorithm which yields a path distance at most one more than the theoretic lower bound. Furthermore, comparisons among uni-directional hypercubes, uni-directional star graphs, and uni-directional alternating group graphs are given. These observations validate the superiority of uni-directional alternating group graphs among known uni-directional topologies.

Keywords: interconnection networks, uni-directional graphs, Cayley graphs, massive parallel computers, alternating group graphs

Full Text () Retrieve PDF document (199905_07.pdf : 63,192 bytes)

Received January 13, 1998; revised March 31 & July 31, 1998; accepted August 7, 1998.
Communicated by Jang-Ping Sheu.