JISE


  [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


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

  Retrieve PDF document (JISE_201202_12.pdf)