Abstract | ||
---|---|---|
A hierarchical cubic network was proposed as an alternative to the hypercube. We use HCN(n) to denote the hierarchical cubic network that contains 2n n-dimensional hypercubes. In this paper, using Gray codes, we construct fault-free hamiltonian cycles in an HCN(n) with n-1 link faults. Since the HCN(n) is regular of degree n+1, the result is optimal. We also construct longest fault-free cycles of length 22n-1 in an HCN(n) with one node fault, and fault-free cycles of length at least 22n-2f in an HCN(n) with f node faults, where 22n is the number of nodes in the HCN(n), f≤n-1 if n=3 or 4, and f≤n if n≥5. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1145/508791.508958 | SAC |
Keywords | Field | DocType |
n-dimensional hypercubes,n-1 link fault,hierarchical cubic network,fault-free cycle,fault-free hamiltonian cycle,node fault,faulty hierarchical cubic network,degree n,gray code,longest fault-free cycle,hypercube,fault tolerant,hamiltonian cycle | Discrete mathematics,Embedding,Hamiltonian (quantum mechanics),Hamiltonian path,Fault tolerant embedding,Gray code,Theoretical computer science,Hypercube,Mathematics | Conference |
ISBN | Citations | PageRank |
1-58113-445-2 | 0 | 0.34 |
References | Authors | |
12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jung-Sheng Fu | 1 | 461 | 24.92 |
Gen-Huey Chen | 2 | 979 | 89.32 |