A Lower Bound for Dilation of an Embedding

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obta...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2015-12, Vol.58 (12), p.3271-3278
Main Authors: Sundara Rajan, R., Manuel, Paul, Rajasingh, Indra, Parthiban, N., Miller, Mirka
Format: Article
Language:English
Subjects:
Algorithms
Computer architecture
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxv021