Graph partitioning: an updated survey

Abstract

AbstractGraph partitioning problem, which is one of the most important topics in graph theory, usually asks for a partition of the vertex set of a graph into pairwise disjoint subsets with various requirements. It comes from the well-known Max-Cut Problem: Given a graph G, find the maximum bipartite subgraph of G. In practice, one often needs to find a partition of a given graph to optimize several quantities simultaneously. Such problems are called judicious partition problems by Bollobás and Scott. In this survey, we present some new results and problems on graph partitioning.

Keywords

• Graph
• digraph
• partition
• bisection
• Max-Cut