TY - JOUR
T1 - On the embedding of a class of regular graphs in a faulty hypercube
AU - Tseng, Yu-Chee
AU - Lai, Ten Hwang
PY - 1996/9/15
Y1 - 1996/9/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=16144366362&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1996.0120
DO - 10.1006/jpdc.1996.0120
M3 - Article
AN - SCOPUS:16144366362
VL - 37
SP - 200
EP - 206
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
SN - 0743-7315
IS - 2
ER -