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

34 Citations (Scopus)

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

Fingerprint

K-ary N-cubes
N-cube
Interconnection networks (circuit switching)
Parallel processing systems
Cycle
Path
Interconnection Networks
Parallel Computing
Vertex of a graph
Fault-tolerant
Arbitrary
Node
Interconnection
Fault
Parallel computing

Keywords

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

Cite this

Dong, Qiang ; Yang, Xiaofan ; Wang, Dajin. / Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links. In: Information Sciences. 2010 ; Vol. 180, No. 1. pp. 198-208.
@article{9e58ad4c126d43a58e9102783223c026,
title = "Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links",
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.",
keywords = "Cycle, Embedding, Fault-tolerance, Interconnection networks, Path, k-Ary n-cube",
author = "Qiang Dong and Xiaofan Yang and Dajin Wang",
year = "2010",
month = "1",
day = "2",
doi = "10.1016/j.ins.2009.09.002",
language = "English",
volume = "180",
pages = "198--208",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",
number = "1",

}

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links. / Dong, Qiang; Yang, Xiaofan; Wang, Dajin.

In: Information Sciences, Vol. 180, No. 1, 02.01.2010, p. 198-208.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Dong, Qiang

AU - Yang, Xiaofan

AU - Wang, Dajin

PY - 2010/1/2

Y1 - 2010/1/2

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

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

KW - Cycle

KW - Embedding

KW - Fault-tolerance

KW - Interconnection networks

KW - Path

KW - k-Ary n-cube

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

U2 - 10.1016/j.ins.2009.09.002

DO - 10.1016/j.ins.2009.09.002

M3 - Article

AN - SCOPUS:70350571716

VL - 180

SP - 198

EP - 208

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 1

ER -