Ring Embedding in an Injured Hypercube

Yu-Chee Tseng, Ten Hwang Lai

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations


We consider the problem of embedding a ring in a hypercube that contains possible faulty nodes. Existing algorithms allow the number of faulty nodes to be at most 2n-Θ(nlogn), where n is the dimension of the hypercube. We propose an embedding scheme that can tolerate up to Θ(2n/2) faulty nodes, largely increasing the number of tolerable faulty nodes in a ring embedding.

Original languageEnglish
Title of host publicationAlgorithms and Applications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages4
ISBN (Electronic)0849389836
StatePublished - 1 Jan 1993
Event1993 International Conference on Parallel Processing, ICPP 1993 - Syracuse, United States
Duration: 16 Aug 199320 Aug 1993

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Conference1993 International Conference on Parallel Processing, ICPP 1993
Country/TerritoryUnited States


Dive into the research topics of 'Ring Embedding in an Injured Hypercube'. Together they form a unique fingerprint.

Cite this