Card image

Scholarly

Volume:1, Issue: 3, 2007 Page No: 503 - 508

International Journal of Information, Control and Computer Sciences

ISSN: 2517-9942

1169 Downloads
Abstract Full Text Download References Share Add to Favorites
DOI:10.5281/zenodo.1330091 BibTeX JSON

A Proof for Bisection Width of Grids

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.
Authors:
Keywords:
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.