Obtaining Balanced Partitions of Grids using Trees
Andreas Emil Feldmann (Dr., ETH Zürich)
We consider the k-BALANCED PARTITIONING problem, which is defined
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
improve on existing 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.
|19.06.2012 17:00||Andreas Emil
Back to the research colloquium site.