Embedding grids, hypercubes, and trees in arrangement graphs

Khaled Day, Anand Tripathi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAlgorithms and Applications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)0849389836
Publication statusPublished - 1993
Externally publishedYes
Event1993 International Conference on Parallel Processing, ICPP 1993 - Syracuse, United States
Duration: Aug 16 1993Aug 20 1993

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Conference1993 International Conference on Parallel Processing, ICPP 1993
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Hardware and Architecture


Dive into the research topics of 'Embedding grids, hypercubes, and trees in arrangement graphs'. Together they form a unique fingerprint.

Cite this