### Page Content

### to Navigation

## Obtaining Balanced Partitions of Grids using Trees

**Andreas Emil Feldmann**** ****(Dr., ETH Zürich)**

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

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.

Date | Speaker | Location | Language |
---|---|---|---|

19.06.2012 17:00 | Andreas Emil Feldmann | TEL 512 | english |