Home | english  | Impressum | Sitemap | KIT

Large-k Partitioning

Large-k Partitioning
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 this thesis, we want to develop an algorithm that is particularly well suited if the number of blocks that the graph needs to be partitioning in is very large.

You should have:

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