On the embedding of a class of regular graphs in a faulty hypercube

Yu-Chee Tseng, Ten Hwang Lai

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In a hypercube of high dimension, the interconnection is quite complex and thus links are likely to fail. In this paper, a general, systematic solution is proposed for the embedding of a group of regular graphs in an injured hypercube with faulty links. These graphs include rings, linear paths, binomial trees, binary trees, meshes, tori, products of the above graphs, and many others. Unlike many existing algorithms which are capable of embedding only one type of graphs, our algorithm embeds the above graphs in a unified way, all centered around a notion called edge matrix.

Original languageEnglish
Pages (from-to)200-206
Number of pages7
JournalJournal of Parallel and Distributed Computing
Volume37
Issue number2
DOIs
StatePublished - 15 Sep 1996

Fingerprint Dive into the research topics of 'On the embedding of a class of regular graphs in a faulty hypercube'. Together they form a unique fingerprint.

Cite this