DocumentCode
1812554
Title
On the embedding of a class of regular graphs in a faulty hypercube
Author
Tseng, Yu-Chee ; Lai, Ten-Hwang
Author_Institution
Dept. of Comput. Sci., Chung-Hua Poly. Inst., Hsin-Chu, Taiwan
fYear
1994
fDate
19-22 Dec 1994
Firstpage
488
Lastpage
495
Abstract
A wide range of graphs with regular structures are shown to be embeddable in an injured hypercube with faulty links. These include rings, linear paths, binomial trees, binary trees, meshes, tori, 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. In many cases, the degree of fault tolerance offered by the algorithm is optimal or near-optimal
Keywords
fault tolerant computing; graphs; hypercube networks; binary trees; binomial trees; embedding; fault tolerance; faulty hypercube; faulty links; injured hypercube; linear paths; meshes; regular graphs; rings; tori; Binary trees; Computer architecture; Computer networks; Computer science; Concurrent computing; Embedded computing; Fault tolerance; Fault tolerant systems; Hypercubes; Tree graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Systems, 1994. International Conference on
Conference_Location
Hsinchu
Print_ISBN
0-8186-6555-6
Type
conf
DOI
10.1109/ICPADS.1994.590360
Filename
590360
Link To Document