𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The bisection width and the isoperimetric number of arrays

✍ Scribed by M Cemil Azizoğlu; Ömer Eğecioğlu

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
229 KB
Volume
138
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that the bisection width, bw(A d ), of a d-dimensional array

i=e Ki where e is the largest index for which ke is even (if it exists, e = 1 otherwise) and Ki = ki-1ki-2 • • • k1. We also show that the edge-isoperimetric number i(A d ) is given by i(A d ) = 1= k d =2 . Furthermore, a bisection and an isoperimetric set are constructed.

📜 SIMILAR VOLUMES

On the bisection width of the transposit
On the bisection width of the transposition network
✍ Kalpakis, Konstantinos; Yesha, Yaacov 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB 👁 3 views

The transposition network T n of order n! is the Cayley graph of the symmetric group S n with generators the set of all transpositions in S n . Finding the bisection width of the transposition network is an open question posed by F. T. Leighton. We resolve this question for n even, by showing that t