The bisection width and the isoperimetric number of arrays

We prove that the bisection width, bw( A d ), of a d-dimensional array A d = P k 1 × P k 2 ×⋯× P k d where k 1⩽ k 2⩽⋯⩽ k d , is given by bw( A d )=∑ i= e d K i where e is the largest index for which k e is even (if it exists, e=1 otherwise) and K i = k i−1 k i−2 ⋯ k 1. We also show that the edge-iso...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2004-03, Vol.138 (1), p.3-12
Main Authors: CEMIL AZIZOGLU, M, EGECIOGLU, Ömer
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Array
Bisection width
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Designs and configurations
Exact sciences and technology
Extremal set
Hamming graph
Isoperimetric number
Mathematics
Product graph
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that the bisection width, bw( A d ), of a d-dimensional array A d = P k 1 × P k 2 ×⋯× P k d where k 1⩽ k 2⩽⋯⩽ k d , is given by bw( A d )=∑ i= e d K i where e is the largest index for which k e is even (if it exists, e=1 otherwise) and K i = k i−1 k i−2 ⋯ k 1. 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(03)00265-8