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

Resilient and Flexible

Ring Embedding in An Injured Hypercube

**Yu-Chee Tseng**

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 is *as large as possible* and can only tolerate up to 2*n* - ŁK() 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 (ŁK(2* ^{n}*/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

Received June 1, 1995; revised April 23, 1996.

Communicated by Wei-Pang Yang.
^{*}This work is supported in part by the National Science Council, R.O.C., under grant number NSC85-2213-E-216-021.