Title :
Embedding Grids, Hypercubes, and Trees in Arrangement Graphs
Author :
Day, Khaled ; Tripathi, Anand
Author_Institution :
University of Bahrain
Abstract :
The use of a new topology, called the arrangement graph, as a viable interconnection scheme for parallel and distributed systems, has been recently proposed and examined. The arrangement graphs represent a rich class of generalized star graphs with many attractive properties, In this paper we obtain (1) unit expansion embeddings of a variety of multi-dimensional grids, (2) dilation 1, 2, 3, and 4 embeddings of hypercubes and (3) hierarchical and greedy spanning trees to support broadcasting and personalized communication in arrangement graphs.
Keywords :
Algorithm design and analysis; Computer science; Fault tolerance; Hypercubes; Instruction sets; Multiprocessor interconnection networks; Network topology; Parallel algorithms; Parallel processing; Tree graphs;
Conference_Titel :
Parallel Processing, 1993. ICPP 1993. International Conference on
Conference_Location :
Syracuse, NY, USA
Print_ISBN :
0-8493-8983-6
DOI :
10.1109/ICPP.1993.76