We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
OPTIMAL EMBEDDING OF HONEYCOMB NETWORKS INTO HYPERCUBES.
- Authors
Bein, Doina; Bein, Wolfgang W.; Brajkovska, Natasa; Latifi, Shahram
- Abstract
We present an optimal embedding of a honeycomb network (boneycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of &frac43; ≈1.33 when n is a power of two. When n is not a power of two, the expansion is &frac163; ≈5.33, 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.
- Subjects
HYPERCUBE networks (Computer networks); HYPERCUBES; COMPUTER networks; PARALLEL processing; MULTIPROCESSORS; PARALLEL programming
- Publication
Parallel Processing Letters, 2004, Vol 14, Issue 3/4, p367
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626404001957