Hamiltonian embedding in crossed cubes with failed links

Research output: Contribution to journalArticle

15 Citations (Scopus)

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
StatePublished - 16 Oct 2012

Fingerprint

Hamiltonians
Fault tolerance
Topology

Keywords

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

Cite this

@article{0cc088f3d47e40c69007156becbb222a,
title = "Hamiltonian embedding in crossed cubes with failed links",
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.",
keywords = "Crossed cube, Hamiltonian cycle, embedding, fault tolerance, faulty links, interconnection networks",
author = "Dajin Wang",
year = "2012",
month = "10",
day = "16",
doi = "10.1109/TPDS.2012.30",
language = "English",
volume = "23",
pages = "2117--2124",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "11",

}

Hamiltonian embedding in crossed cubes with failed links. / Wang, Dajin.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 23, No. 11, 6133282, 16.10.2012, p. 2117-2124.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Hamiltonian embedding in crossed cubes with failed links

AU - Wang, Dajin

PY - 2012/10/16

Y1 - 2012/10/16

N2 - 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.

AB - 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.

KW - Crossed cube

KW - Hamiltonian cycle

KW - embedding

KW - fault tolerance

KW - faulty links

KW - interconnection networks

UR - http://www.scopus.com/inward/record.url?scp=84867292809&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2012.30

DO - 10.1109/TPDS.2012.30

M3 - Article

AN - SCOPUS:84867292809

VL - 23

SP - 2117

EP - 2124

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 11

M1 - 6133282

ER -