- Title
- A lower bound for dilation of an embedding
- Creator
- Sundara Rajan, R.; Manuel, Paul; Rajasingh, Indra; Parthiban, N.; Miller, Mirka
- Relation
- The Computer Journal Vol. 58, Issue 12, p. 3271-3278
- Publisher Link
- http://dx.doi.org/10.1093/comjnl/bxv021
- Publisher
- Oxford University Press
- Resource Type
- journal article
- Date
- 2015
- Description
- 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.
- Subject
- embedding; dilation; circulant network; triangular grid; Tower of Hanoi; Sierpinski gasket graph
- Identifier
- http://hdl.handle.net/1959.13/1321483
- Identifier
- uon:24372
- Identifier
- ISSN:0010-4620
- Language
- eng
- Reviewed
- Hits: 2142
- Visitors: 1654
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|