Friday, September 14, 2012
3:30 pm, MC 5158

Andreas Feldmann
University of Waterloo

Obtaining Balanced Partitions of Grids using Trees

We consider the k-BALANCED PARTITIONING problem, which is defined as follows. Find the minimum number of edges in a graph that, when cut, partition the vertices into k (almost) equally sized sets. Amongst others, the problem derives its importance from the need to distribute data within a parallel computing architecture. In this setting we are particularly interested in 2D finite element model (FEM) simulations. We therefore model the input as a regular quadrilateral tiling of the plane. More precisely, we focus on solid grid graphs. These are finite connected subgraphs of the infinite 2D grid without holes.
Trees often help to find solutions to the problem on grid graphs. This is surprising since trees and grids are very different from a combinatorial point of view. We show that algorithms for trees help to divise algorithms for grids, both in the special case when k=2 (the BISECTION problem) and when k can take arbitrary values. Additionally we prove that the k-BALANCED PARTITIONING problem experiences similar hardness on grids and trees.