A New Heuristic for Partitioning the Nodes of a Graph

There is a class of graph partitioning algorithms which improve an initial partition by interchanging nodes between the subsets of the initial partition. These algorithms tend to require long running times because usually many trials must be made before the right combination of nodes to interchange is found. In this paper we describe a fast procedure for determining sets of nodes to interchange in order to improve an initial partition.