Optimal fault-tolerant embedding of paths in twisted cubes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

45 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)205-214
Journal / PublicationJournal of Parallel and Distributed Computing
Volume67
Issue number2
Publication statusPublished - Feb 2007

Abstract

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQn (V, E) denote the n-dimensional twisted cube. We prove that a path of length l can be embedded between any two distinct nodes with dilation 1 for any faulty set F ⊂ V (TQn) ∪ E (TQn) with | F | ≤ n - 3 and any integer l with 2n - 1 - 1 ≤ l ≤ | V (TQn - F) | - 1 (n ≥ 3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size | F | for a successful embedding are tight. That is, the result does not hold if l ≤ 2n - 1 - 2 or | F | ≥ n - 2. We also extend the result on (n - 3)-Hamiltonian connectivity of TQn in the literature. © 2006 Elsevier Inc. All rights reserved.

Research Area(s)

  • Dilation, Embedding, Fault tolerant, Parallel computing system, Path, Twisted cube