Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes

被引：81

作者：

Bae, MM

Bose, B

机构：

[1] IBM Corp, Unix Clustering Infrastruct, Poughkeepsie, NY 12601 USA

[2] Oregon State Univ, Sch Elect Engn & Comp Sci, Corvallis, OR 97331 USA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2003年 / 52卷 / 10期

基金：

美国国家科学基金会;

关键词：

k-ary n-cubes; hypercube; Lee distance; Lee distance gray codes; binary Gray codes; Hamiltonian cycle;

D O I：

10.1109/TC.2003.1234525

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Solutions for decomposing a higher dimensional torus to edge disjoint lower dimensional tori, in particular, edge disjoint Hamiltonian cycles are obtained based on the coding theory approach. First, Lee distance Gray codes in Z(k)(n) are presented and then it is shown how these codes can directly be used to generate edge disjoint Hamiltonian cycles in k-ary n-cubes. IFurther, some new classes of binary Gray codes are designed from these Lee distance Gray codes and, using these new classes of binary Gray codes, edge disjoint Hamiltonian cycles in hypercubes are generated.

引用

页码：1271 / 1284

页数：14

共 20 条

[1]

Alspach Brian, 1990, CYCLES RAYS, P9

[2]

[Anonymous], SIAM J DISCRETE MATH

[3]

BAE M, 1996, THESIS OREGON STATE

[4] HAMILTONIAN DECOMPOSITION OF CAYLEY-GRAPHS OF DEGREE-4 [J].

BERMOND, JC ;

FAVARON, O ;

MAHEO, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :142-153

[5]

Bertsekas Dimitri P., 1989, PARALLEL DISTRIBUTED

[6]

BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437

[7]

BORKAR S, 1988, IEEE P SUPERCOMPUTER, P330

[8] LEE DISTANCE AND TOPOLOGICAL PROPERTIES OF K-ARY N-CUBES [J].

BOSE, B ;

BROEG, B ;

KWON, Y ;

ASHIR, Y .

IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (08) :1021-1030

[9]

BROEG B, 1998, TELECOMMUN SYST, P21

[10]

CULL LP, 1994, P 6 IEEE S PAR DISTR, P696

← 1 2 →