JISE


  [1] [2] [3] [4] [5] [6] [7] [8]


Journal of Information Science and Engineering, Vol. 12 No. 4, pp. 567-583


Resilient and Flexible Ring Embedding in An Injured Hypercube


Yu-Chee Tseng
Department of Computer Science and Information Engineering 
National Central University 
Chung-Li, Taiwan 32054, R.O.C.


    This paper presents an algorithm for embedding a ring of a given size in a damaged n-cube. Existing algorithms all attempt to find a ring which isas large as possible and can only tolerate up to 2n - Θ(JISE) faulty nodes. There are two contributions made in this paper. First, we have identified a problem which is closer to a realistic situation in mapping a parallel algorithm to a hypercube machine. Second, the proposed algorithm can tolerate a significantly larger number (Θ(2n/2)) of faulty nodes, and always embeds a ring with congestion 1 and dilation of at most 2. This result compares favorably to existing algorithms in embedding congestion, embedding dilation, or degrees of fault tolerance.


Keywords: graph embedding, hypercube, ring, linear path, fault tolerance

  Retrieve PDF document (JISE_199604_05.pdf)