Title :
Embedding and reconfiguration of binary trees in faulty hypercubes
Author :
Yang, Pei-Ji ; Raghavendra, C.S.
Author_Institution :
Dept. of Electr. Eng.-Syst., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
Considers the problem of embedding and reconfiguring binary tree structures in faulty hypercubes. The authors assume that the number of faulty nodes is about n, where n is the number of dimensions of the hypercube; they further assume that the location of faulty nodes are known. The embedding techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains at most one faulty node. Using this approach, two distributed schemes are provided for embedding and reconfiguration of binary trees in faulty hypercubes
Keywords :
hypercube networks; trees (mathematics); binary tree structures; embedding; faulty hypercubes; free dimension; reconfiguration; Binary trees; Computer science; Costs; Delay effects; Fault tolerance; Fault tolerant systems; Hardware; Hypercubes; Multiprocessing systems; Time measurement;
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
DOI :
10.1109/IPPS.1992.223080