Graph Partitioning

Graph partitioning is one of the key problems in several applications such as VLSI design or parallel programming where structural properties can be expressed as graphs. Often, it is necessary to find clusterings of these graphs fulfilling certain constraints like equality in size or weight or minimal numbers of edges crossing cluster boundaries. The corresponding partitioning problem is NP-complete, i.e., efficient algorithms solving it to optimality currently do not exist. Unfortunately, even approximation algorithms which are able to split a graph into a number of pieces considering certain cost functions are hard to find and are usually very time-consuming. A way to deal with this problem is to view it as a series of bisections which are applied recursively. For the bisection problem several efficient heuristics do exist.

• Theory of graph bisection

• Bisection heuristics (especially HS)

• Applications of various kind

• A collection of graphs