loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Internode Distance and Optimal Routing in a Class of Alternating Group Networks
December 2006 (vol. 55 no. 12)
pp. 1645-1648
ASCII Text
x 
 
Baoxing Chen, Wenjun Xiao, Behrooz Parhami, "Internode Distance and Optimal Routing in a Class of Alternating Group Networks," IEEE Transactions on Computers, vol. 55, no. 12, pp. 1645-1648, December, 2006.
 
 
BibTex
x
 
@article{ 10.1109/TC.2006.199,
author = {Baoxing Chen and Wenjun Xiao and Behrooz Parhami},
title = {Internode Distance and Optimal Routing in a Class of Alternating Group Networks},
journal ={IEEE Transactions on Computers},
volume = {55},
number = {12},
issn = {0018-9340},
year = {2006},
pages = {1645-1648},
doi = {http://doi.ieeecomputersociety.org/10.1109/TC.2006.199},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - Internode Distance and Optimal Routing in a Class of Alternating Group Networks
IS - 12
SN - 0018-9340
SP1645
EP1648
EPD - 1645-1648
A1 - Baoxing Chen,
A1 - Wenjun Xiao,
A1 - Behrooz Parhami,
PY - 2006
KW - Alternating group graph
KW - Cayley graph
KW - diameter
KW - interconnection network
KW - internode distance
KW - optimal routing
KW - permutation group
KW - regular graph
KW - shortest-path routing.
VL - 55
JA - IEEE Transactions on Computers
ER -
 
Alternating group graphs AG_{n}, 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, AN_{n}, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AG_{n}. For example, AN_{n} has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AG_{n}, 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 AN_{n} and present an optimal (shortest-path) routing algorithm for this class of networks.

[1] S.B. Akers and B. Krishnamurthy, “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. Computers, vol. 38, pp.555-566, 1989.
[2] E. Cheng and M.J. Lipman, “Orienting Split-Stars and Alternating Group Graphs,” Networks, vol. 35, no. 2, pp. 139-144, 2000.
[3] Y.O. Hamidoune, A.S. Llado, and O. Serra, “The Connectivity of Hierarchical Cayley Digraphs,” Discrete Applied Math., vols. 37/38, pp.175-180, 1992.
[4] J.S. Jwo, S. Lakshmivarahan, and S.K. Dhall, “A New Class of Interconnection Networks Based on the Alternating Groups,” Networks, vol. 23, pp. 315-326, 1993.
[5] S. Lakshmivarahan, J.S. Jwo, and S.K. Dhall, “Symmetry in Interconnection Networks Based on Cayley Graphs of Permutations: A Survey,” Parallel Computing, vol. 19, pp. 361-407, 1993.
[6] S. Latifi, “On the Fault-Diameter of the Star Graph,” Information Processing Letters, vol. 46, pp. 143-150, 1993.
[7] B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures. Plenum Press, 1999.
[8] D.K. Pradhan and F.J. Meyer, “Communication Structures in Fault-Tolerant Distributed Systems,” Networks, vol. 23, pp. 379-389, 1993.
[9] Y. Roichman, “Expansion Properties of Cayley Graphs of the Alternating Groups,” J. Combinatorial Theory, vol. 79(A), pp. 281-279, 1997.
[10] J. Youhu, “A New Class of Cayley Networks Based on the Alternating Groups,” Applied Math.—JCU, vol. 14(A), no. 2, pp. 235-239, 1998 (in Chinese).

Index Terms:
Alternating group graph, Cayley graph, diameter, interconnection network, internode distance, optimal routing, permutation group, regular graph, shortest-path routing.
Citation:
Baoxing Chen, Wenjun Xiao, Behrooz Parhami, "Internode Distance and Optimal Routing in a Class of Alternating Group Networks," IEEE Transactions on Computers, vol. 55, no. 12, pp. 1645-1648, Dec. 2006, doi:10.1109/TC.2006.199
Usage of this product signifies your acceptance of the Terms of Use.