Hamiltonian embedding in crossed cubes with failed links

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

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.

Original languageEnglish
Article number6133282
Pages (from-to)2117-2124
Number of pages8
JournalIEEE Transactions on Parallel and Distributed Systems
Volume23
Issue number11
DOIs
Publication statusPublished - 16 Oct 2012

    Fingerprint

Keywords

  • Crossed cube
  • Hamiltonian cycle
  • embedding
  • fault tolerance
  • faulty links
  • interconnection networks

Cite this