Home | english  | Impressum | Sitemap | KIT

Better Recursive Bisection with Local Search

Better Recursive Bisection with Local Search
Forschungsthema:Graph Partitioning

Sebastian Schlag, Christian Schulz

Topic Description

Subdividing a problem into manageable pieces is a critical task in effectively parallelizing computation and even accelerating sequential computation. A key method that has received a lot of attention for doing so is graph partitioning.  The basic graph partitioning problem is to split a graph's vertex set into a given number of almost equally sized blocks while minimizing a suitable objective function.  The simplest and perhaps most common form of graph partitioning asks for the vertex set to be partitioned into k blocks, while minimizing the number of edges between the blocks (called cut edges). Even this most basic variant is NP-hard, by a reduction from 3SAT. Graph partitioning has many application areas, including VLSI, scientific computing, designing scalable distributed systems, genome sequencing, and routing in road networks. The role that graph partitioning plays in each of these applications, is one of efficiency. Given its usage in many varied areas, it is critical to understand how a high-quality graph partition can be computed and used in practice.

In thesis we want to combine different stages in recursive bisection (a method to tackle the problem) with local search to get higher solution quality.

You should have:

  • solid knowledge in algorithms and data structures
  • good knowledge in C++ and OpenMP