In the paper, the authors show that the two uni-directional hypercubes, namely UHC1n and UHC2n, proposed by Chou and Du as interconnection schemes, are Hamiltonian. In addition, the authors show that if n is even, both architectures are vertex symmetric, and that if n is odd, both architectures have exactly two vertex-symmetric components. Furthermore, the study of the symmetry leads to an effective analysis of the maximum delay of one-port one-to-all broadcasting for either architecture which is at most ⌈1.5n⌉.
References
-
-
1)
-
S.T. Tan ,
D.H.C. Du
.
Embedded unidirectional incomplete hypercubes for optical networks.
IEEE Trans. Comm.
,
9 ,
1284 -
1289
-
2)
-
V. Faber ,
W. Moore ,
W.Y.C. Chen
.
Cycle prefix digraphs for symmetric interconnection networks.
Networks
,
641 -
649
-
3)
-
K. Day ,
A. Tripathi
.
Unidirectional star graphs.
Info. Proc. Lett.
,
123 -
129
-
4)
-
Chern, S., Tuan, T., Jwo, J.: `Container problem for maximum fault tolerantuni-directional hypercubes', Technical report, 1994.
-
5)
-
S.B. Akers ,
B. Krishnamurthy
.
A group-theoretic model for symmetricinterconnection networks.
IEEE Trans. Comput.
,
555 -
566
-
6)
-
S. Lakshmivarahan ,
S.K. Dhall
.
(1990)
Analysis and design of parallel algorithms.
-
7)
-
L.M. Ni ,
P.K. McKinley
.
A survey of wormhole routing techniques in direct networks.
IEEE Computer
,
62 -
76
-
8)
-
Chou, C.H., Du, D.H.C.: `Uni-directional hypercubes', Proceedings of Supercomputing'90, p. 254–263.
-
9)
-
R.J. Vetter ,
D.H.C. Du
.
Distributed computing in an environment based on high speed optical networks.
IEEE Computer
,
2 ,
8 -
18
-
10)
-
Comellas, F., Fiol, M.A.: `Vertex symmetric digraphs with small diameter', Technique report, February 1992.
-
11)
-
F.T. Leighton
.
(1992)
Introduction to parallel algorithms and architectures: Arrays, trees,hypercubes.
-
12)
-
M. Lin ,
R. Tsang ,
D.H.C. Du
.
Performance evaluation of CM-5 interconnection networks.
J. Parallel Distrib. Computing
-
13)
-
Y.O. Hamidoune ,
A.S. Llado ,
O. Serra
.
The connectivity of hierarchical cayley digraphs.
Disc. Appl. Math.
,
275 -
280
-
14)
-
S. Lakshmivarahan ,
J. Jwo ,
S.K. Dhall
.
Symmetry in interconnection networks based on cayley graphs of permutation groups: A survey.
Parallel Computing
,
361 -
407
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_19970914
Related content
content/journals/10.1049/ip-cdt_19970914
pub_keyword,iet_inspecKeyword,pub_concept
6
6