Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]

¡@

Journal of Information Science and Engineering, Vol. 28 No. 2, pp. 419-426 (March 2012)

Fault-Tolerant Cycle Embedding in Restricted Hypercube-like Networks with More Faulty Nodes*

QIANG DONG1,2,3 AND XIAO-FAN YANG3
 1Web Science Center
2National Computer Experimental Teaching Demonstration Center
University of Electronic Science and Technology of China
Chengdu 611731, P.R. China
3College of Computer Science
Chongqing University
Chongqing 400044, P.R. China

The hypercube-like networks are a class of important generalization of the popular hypercube interconnection networks for parallel computing. This paper is concerned with the fault-tolerant cycle embedding ability of a subclass of hypercube-like networks, called restricted hypercube-like networks (RHLNs, for short), which include most of the well-known hypercube variants, such as the twisted cubes, the crossed cubes, the locally twisted cubes, and the Mobius cubes. We show that for n >= 5 and f <= 2n - 7, a fault-free cycle of length at least 2n - f - (n - 5) can be embedded in an n-dimensional RHLN with f faulty nodes. Our work extends the previous known result in the sense of maximum number of faulty nodes tolerable in an RHLN.

Keywords: interconnection networks, hypercube-like network, cycle embedding, faulttolerance, parallel computing

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201203_12.pdf)

Received May 11, 2010; revised October 5, 2010; accepted November 22, 2010.
Communicated by Xiaohong Jiang.
* This work was supported by National Nature Science Foundation of China (#10771227, #60973120, #60903073, #61003231), and Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry (#GGRYJJ08-2).