Algorithms for Graph Partitioning: A Survey

Abstract

The graph partitioning problem is as follows. Given a graph G = (N, E) (where N is a set of weighted nodes and E is a set of weighted edges) and a positive integer p , find p subsets N1 , N2 ,... Np of N such thatthe union set of Ni where i = 1...p equals N and Ni is disjoint from Nj for i =/ j , W(i)~W/p where i = 1, 2...p , where W(i) and W are the sums of the node weights in Ni and N , respectively,the cut size, i.e., the sum of the weights of edges crossing between subsets is minimized.This problem is of interest in areas such as VLSI placement and routing, and efficient parallel implementations of finte element methods. In this survey we summarize the state-of-the-art of sequential and parallel graph partitioning problems.