On Partitioning Grids into Equal Parts

Authors

  • S. L. Bezrukov
  • B. Rovan

Abstract

Let an edge cut partition the vertex set of an n-dimensional quadratic grid with the side length a into k subsets A1, … , Ak with ... . We consider the problem of determining the minimal size c (n,k,a) of such a cut and present its asymptotic c (n,k,a) ~ nan-1  as a, k ®   and k/an ® 0. The same asymptotic holds for partitioning of the n-dimensional torus. We present also some heuristics, which provide better partitioning for n = 2 and small k.

Downloads

Download data is not yet available.

Published

2012-03-05

How to Cite

Bezrukov, S. L., & Rovan, B. (2012). On Partitioning Grids into Equal Parts. Computing and Informatics, 16(2), 153–165. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/666