✦ LIBER ✦

On the area of hypercube layouts

✍ Scribed by Ronald I. Greenberg; Lee Guan

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 106 KB
Volume: 84
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00218-1

No coin nor oath required. For personal study only.

✦ Synopsis

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N 2 nodes in the plane, in an N × N grid arrangement, uses 2N/3 + 1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).

📜 SIMILAR VOLUMES

Nearly optimal three dimensional layout

Nearly optimal three dimensional layout of hypercube networks

✍ Tiziana Calamoneri; Annalisa Massini 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

Randomized Selection on the Hypercube

✍ Sanguthevar Rajasekaran 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 258 KB

In this paper, we present randomized algorithms for selection on the hypercube. We identify two variants of the hypercube, namely, the sequential model and the parallel model. In the sequential model, any node at any time can handle only communication along a single incident edge, whereas in the par

Radix sort on the hypercube

✍ Giovanni Manzini 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 640 KB

On the Achromatic Number of Hypercubes

✍ Yuval Roichman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su

On the galactic number of a hypercube

✍ Michael Fellows; Mark Hoover; Frank Harary 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 298 KB

A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determini

Parallelizing object recognition on the

Parallelizing object recognition on the hypercube

✍ Suchendra M Bhandarkar 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 635 KB