Hamiltonian Embedding in Crossed Cubes with Failed Links

The crossed cube is a prominent variant of the well known, highly regular-structured hypercube. In [24], it is shown that due to the loss of regularity in link topology, generating Hamiltonian cycles, even in a healthy crossed cube, is a more complicated procedure than in the hypercube, and fewer Ha...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2012-11, Vol.23 (11), p.2117-2124
Main Author: Wang, Dajin
Format: Article
Language:English
Subjects:
Algorithms
Crossed cube
Cubes
embedding
Fault tolerance
Fault tolerant systems
faulty links
Hamiltonian cycle
Hypercubes
Interconnection
interconnection networks
Joining processes
Lead
Links
Networks
Proposals
Regularity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The crossed cube is a prominent variant of the well known, highly regular-structured hypercube. In [24], it is shown that due to the loss of regularity in link topology, generating Hamiltonian cycles, even in a healthy crossed cube, is a more complicated procedure than in the hypercube, and fewer Hamiltonian cycles can be generated in the crossed cube. Because of the importance of fault-tolerance in interconnection networks, in this paper, we treat the problem of embedding Hamiltonian cycles into a crossed cube with failed links. We establish a relationship between the faulty link distribution and the crossed cube's tolerability. A succinct algorithm is proposed to find a Hamiltonian cycle in a CQ n tolerating up to n-2 failed links.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2012.30