Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links

✍ Scribed by Dajin Wang

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 235 KB
• Volume: 61
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1681

✦ Synopsis

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