OPTIMAL EMBEDDING OF HONEYCOMB NETWORKS INTO HYPERCUBES
- 1 September 2004
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 14 (03n04) , 367-375
Abstract
We present an optimal embedding of a honeycomb network (honeycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of [ ] when n is a power of two. When n is not a power of two, the expansion is [ ], which we conjecture to be near optimal. For a honeycomb mesh, the dilation of the embedding is 1. For a honeycomb torus, the dilation can be as large as 2⌈ log n⌉+3, because of the extra links connecting symmetric opposite nodes of degree two. A honeycomb network, built recursively using hexagon tessellation, is a multiprocessor interconnection network, and also a Cayley graph, and it is better than the planar mesh with the same number of nodes in terms of degree, diameter, number of links, and bisection width.Keywords
This publication has 8 references indexed in Scilit:
- A unified formulation of honeycomb and diamond networksIEEE Transactions on Parallel and Distributed Systems, 2001
- ALL-TO-ALL BROADCASTING ALGORITHMS ON HONEYCOMB NETWORKS AND APPLICATIONSParallel Processing Letters, 1999
- Honeycomb tori are HamiltonianInformation Processing Letters, 1999
- Honeycomb networks: Topological properties and communication algorithmsIEEE Transactions on Parallel and Distributed Systems, 1997
- Enumeration of Polyhex Hydrocarbons to h = 17Journal of Chemical Information and Computer Sciences, 1995
- A digital geometry for hexagonal pixelsImage and Vision Computing, 1989
- Computer graphics on a hexagonal gridComputers & Graphics, 1984
- Homogeneous distribution of frequencies in a regular hexagonal cell systemIEEE Transactions on Vehicular Technology, 1982