Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426780 | Information and Computation | 2013 | 12 Pages |
Abstract
The k-ary n-cube has been one of the most popular interconnection networks for distributed-memory parallel systems. In this paper, we study the problem of embedding cycles of various lengths into faulty k-ary n-cubes. It is proved that a faulty k-ary n -cube with fvfv faulty vertices and fefe faulty edges admits a fault-free cycle of every even length from 4 to kn−2fvkn−2fv if k⩾4k⩾4 is even and fv+fe⩽2n−2fv+fe⩽2n−2. Furthermore, we show that every healthy edge of the faulty k-ary n -cube lies on a fault-free cycle of every even length from 4 to kn−2fvkn−2fv if k⩾4k⩾4 is even and fv+fe⩽2n−3fv+fe⩽2n−3. The results are optimal with respect to the number of vertex and edge faults tolerated.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shiying Wang, Jing Li, Shangwei Lin, Ruixia Wang,