Resilient and flexible ring embedding in an injured hypercube

Yu-Chee Tseng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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 2n - Θ(√nlogn) 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.

Original languageEnglish
Pages (from-to)567-583
Number of pages17
JournalJournal of Information Science and Engineering
Volume12
Issue number4
StatePublished - 1 Dec 1996

Keywords

  • Fault tolerance
  • Graph embedding
  • Hypercube
  • Linear path
  • Ring

Fingerprint Dive into the research topics of 'Resilient and flexible ring embedding in an injured hypercube'. Together they form a unique fingerprint.

Cite this