A new class of interconnection networks based on the alternating group

✍ Scribed by Jung-Sing Jwo; S. Lakshmivarahan; S. K. Dhall

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 724 KB
• Volume: 23
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230230414

✦ Synopsis

This paper introduces a new class of interconnection scheme based on the Cayley graph of the alternating group. It is shown that this class of graphs are edge symmetric and 2-transitive. We then describe an algorithm for (a) packet routing based on the shortest path analysis, (b) finding a Hamiltonian cycle, (c) ranking and unranking along the chosen Hamiltonian cycle, (d) unit expansion and dilation three embedding of a class of two-dimensional grids, (e) unit dilation embedding of a variety of cycles, and (f) algorithm for broadcasting messages. The paper concludes with a short analysis of contention resulting from a typical communication scheme. Although this class of graphs does not possess many of the symmetry properties of the binary hypercube, with respect to the one source broadcasting, these graphs perform better than does a hypercube, and with respect to the contention problem, these graphs perform better than do the star graphs and are close to the hypercube.