On Partitioning Grids into Equal Parts
Sergei L. Bezrukov, Branislav Rovan · 1997
Let an edge cut partition the vertex set of an n-dimensional quadratic grid with the side length a into k subsets A 1 ; :::; A k with jjA i j \\Gamma jA j jj 1. 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) ¸ na n\\Gamma1 n p k as a; k !1 and k=a n ! 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. 1 Introduction Various aspects of graph partitioning are of a particular interest in theoretical computer science and they arise in various applications. In our paper we study partitioning of grids -- a kind of graphs which appear quite naturally, e.g., in numerical computations. Application of the finite elements method for solving differential equations requires partitioning of the underlying area into simple figures - e.g. squares - and assigning the nodes of the partition to the processors of a para...