Search

A number of low degree and, thus, low complexity, Cayley-graph interconnection structures, such as honeycomb and diamond networks, are known to be derivable by systematic pruning of 2D or 3D tori. In this paper, we extend these known pruning schemes via a general algebraic construction based on commutative groups. We show that, under certain conditions, Cayley graphs based on the constructed groups are pruned networks when Cayley graphs of the original commutative groups are κD tori. Thus, our results offer a general mathematical framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees and, thus, smaller VLSI layout and simpler physical packaging. Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as honeycomb and diamond networks. [ABSTRACT FROM AUTHOR]

Alternating group graphs AGn, studied by Jwo and others, Constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, ANn, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANn has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANn and present an optimal (shortest-path) routing algorithm for this class of networks. [ABSTRACT FROM AUTHOR]