Embedding Grids, Hypercubes, and Trees in Arrangement Graphs
- 1 August 1993
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 20 references indexed in Scilit:
- Embedding of cycles and grids in star graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A comparative study of topological properties of hypercubes and star graphsIEEE Transactions on Parallel and Distributed Systems, 1994
- Arrangement graphs: a class of generalized star graphsInformation Processing Letters, 1992
- Optimum broadcasting and personalized communication in hypercubesIEEE Transactions on Computers, 1989
- On multidimensional arrays of processorsIEEE Transactions on Computers, 1988
- On embedding rectangular grids in hypercubesIEEE Transactions on Computers, 1988
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- Optimal simulations of tree machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- The Illiac IV systemProceedings of the IEEE, 1972