Embedding grids, hypercubes, and trees in arrangement graphs

Khaled Day; Anand Tripathi

doi:10.1109/ICPP.1993.76

Embedding grids, hypercubes, and trees in arrangement graphs

Khaled Day, Anand Tripathi

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

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.

Original language	English (US)
Title of host publication	Algorithms and Applications
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	65-72
Number of pages	8
ISBN (Electronic)	0849389836
DOIs	https://doi.org/10.1109/ICPP.1993.76
State	Published - 1993
Event	1993 International Conference on Parallel Processing, ICPP 1993 - Syracuse, United States Duration: Aug 16 1993 → Aug 20 1993

Publication series

Name	Proceedings of the International Conference on Parallel Processing
Volume	3
ISSN (Print)	0190-3918

Conference

Conference	1993 International Conference on Parallel Processing, ICPP 1993
Country/Territory	United States
City	Syracuse
Period	8/16/93 → 8/20/93

Bibliographical note

Publisher Copyright:
© 1993 IEEE.

Publisher link

10.1109/ICPP.1993.76

Find It

Find It at U of M Libraries

Cite this

Day, K & Tripathi, A 1993, Embedding grids, hypercubes, and trees in arrangement graphs. in Algorithms and Applications., 4134247, Proceedings of the International Conference on Parallel Processing, vol. 3, Institute of Electrical and Electronics Engineers Inc., pp. 65-72, 1993 International Conference on Parallel Processing, ICPP 1993, Syracuse, United States, 8/16/93. https://doi.org/10.1109/ICPP.1993.76

@inproceedings{0479465af45b4fb8ab72fca52a221b1b,

title = "Embedding grids, hypercubes, and trees in arrangement graphs",

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.",

author = "Khaled Day and Anand Tripathi",

note = "Publisher Copyright: {\textcopyright} 1993 IEEE.; 1993 International Conference on Parallel Processing, ICPP 1993 ; Conference date: 16-08-1993 Through 20-08-1993",

year = "1993",

doi = "10.1109/ICPP.1993.76",

language = "English (US)",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "65--72",

booktitle = "Algorithms and Applications",

}

TY - GEN

T1 - Embedding grids, hypercubes, and trees in arrangement graphs

AU - Day, Khaled

AU - Tripathi, Anand

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85031555718&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031555718&partnerID=8YFLogxK

U2 - 10.1109/ICPP.1993.76

DO - 10.1109/ICPP.1993.76

M3 - Conference contribution

AN - SCOPUS:85031555718

T3 - Proceedings of the International Conference on Parallel Processing

SP - 65

EP - 72

BT - Algorithms and Applications

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1993 International Conference on Parallel Processing, ICPP 1993

Y2 - 16 August 1993 through 20 August 1993

ER -

Embedding grids, hypercubes, and trees in arrangement graphs

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this