Block Exchange in Graph Partitioning Chapter uri icon


  • In a seminal paper (An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, 49 (1970), pp. 291307), Kernighan and Lin propose a pair exchange algorithm for approximating the solution to min-cut graph partitioning problems. In their algorithm, a vertex from one set in the current partition is exchanged with a vertex in the other set to reduce the sum of the weights of cut edges. The exchanges continue until the total weight of the cut edges is no longer reduced. In this paper, we consider a block exchange algorithm in which a group of vertices from one set is exchanged with a group of vertices from the other set in order to minimize the sum of the weights of cut edges. An optimal choice for the exchanged vertices is the solution to a quadratic programming problem.

author list (cited authors)

  • Hager, W. W., Park, S. C., & Davis, T. A.

citation count

  • 3

complete list of authors

  • Hager, William W||Park, Soon Chul||Davis, Timothy A

editor list (cited editors)

  • Pardalos, P. M.

Book Title

  • Approximation and Complexity in Numerical Optimization

publication date

  • January 2000