A Proof for Bisection Width of Grids

Authors: Kemal Efe, Gui-Liang Feng

Abstract:

The optimal bisection width of r-dimensional N× · · ·× N grid is known to be Nr-1 when N is even, but when N is odd, only approximate values are available. This paper shows that the exact bisection width of grid is Nr -1 N-1 when N is odd.

Keywords: Grids, Parallel Architectures, Graph Bisection, VLSI Layouts.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330091

References:

[1] F. T. Leighton, "Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes," Morgan Kaufmann, 1992.
[2] C. H. Papadimitrou and M. Sideri, "The Bisection Width of Grid Graphs," Theory of Computing Systems, Vol. 29, No. 2, March 1996, pp. 97-110.
[3] C. D. Thompson, "A Complexity Theory for VLSI," PhD thesis, Carnegie-Mellon University, August 1980.