Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links |
| |
Authors: | Qiang Dong Xiaofan Yang |
| |
Affiliation: | a College of Computer Science, Chongqing University, Shapingba Street, Shapingba District, Chongqing 400044, China b Department of Computer Science, Montclair State University, Montclair, NJ 07043, USA |
| |
Abstract: | The k-ary n-cube, denoted by , 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|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal. |
| |
Keywords: | Interconnection networks k-Ary n-cube Embedding Path Cycle Fault-tolerance |
本文献已被 ScienceDirect 等数据库收录! |
|