Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

Qiang Dong, Xiaofan Yang, Dajin Wang

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

The k-ary n-cube, denoted by Qnk, is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n ≥ 2. We show that when | F | ≤ 2 n - 2, there exists a cycle of any length from 3 to | V (Qn3 - F) | in Qn3 - F. We also prove that when | F | ≤ 2 n - 3, there exists a path of any length from 2 n - 1 to | V (Qn3 - F) | - 1 between two arbitrary nodes in Qn3 - F. Since the k-ary n-cube is regular of degree 2 n, the fault-tolerant degrees 2 n - 2 and 2 n - 3 are optimal.

Original languageEnglish
Pages (from-to)198-208
Number of pages11
JournalInformation Sciences
Volume180
Issue number1
DOIs
StatePublished - 2 Jan 2010

Keywords

  • Cycle
  • Embedding
  • Fault-tolerance
  • Interconnection networks
  • Path
  • k-Ary n-cube

Fingerprint Dive into the research topics of 'Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links'. Together they form a unique fingerprint.

  • Cite this