Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links

Research output: Contribution to journalArticle

70 Citations (Scopus)

Abstract

It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n-2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n-1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that F≤n-1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n-1 is the maximum number for F that can be tolerated, F being an arbitrary set of faulty links.

Original languageEnglish
Pages (from-to)545-564
Number of pages20
JournalJournal of Parallel and Distributed Computing
Volume61
Issue number4
DOIs
StatePublished - 1 Apr 2001

Fingerprint

Hamiltonians
Hamiltonian circuit
N-cube
Hypercube
Flip
Fault-tolerant Embedding
Regular hexahedron
n-dimensional
Arbitrary
Vertex of a graph

Keywords

  • Embedding; fault tolerance; folded hypercube; Hamiltonian cycle; link fault

Cite this

@article{df61aef5f2954001b53e933255143452,
title = "Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links",
abstract = "It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n-2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n-1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that F≤n-1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n-1 is the maximum number for F that can be tolerated, F being an arbitrary set of faulty links.",
keywords = "Embedding; fault tolerance; folded hypercube; Hamiltonian cycle; link fault",
author = "Dajin Wang",
year = "2001",
month = "4",
day = "1",
doi = "10.1006/jpdc.2000.1681",
language = "English",
volume = "61",
pages = "545--564",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "4",

}

Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links. / Wang, Dajin.

In: Journal of Parallel and Distributed Computing, Vol. 61, No. 4, 01.04.2001, p. 545-564.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links

AU - Wang, Dajin

PY - 2001/4/1

Y1 - 2001/4/1

N2 - It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n-2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n-1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that F≤n-1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n-1 is the maximum number for F that can be tolerated, F being an arbitrary set of faulty links.

AB - It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n-2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n-1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that F≤n-1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n-1 is the maximum number for F that can be tolerated, F being an arbitrary set of faulty links.

KW - Embedding; fault tolerance; folded hypercube; Hamiltonian cycle; link fault

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

U2 - 10.1006/jpdc.2000.1681

DO - 10.1006/jpdc.2000.1681

M3 - Article

AN - SCOPUS:0038248737

VL - 61

SP - 545

EP - 564

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 4

ER -