A New Heuristic for Partitioning the Nodes of a Graph

Authors:
  • EBEarl R. Barnes
    Earl R. Barnes
  • AVAnthony Vannelli
    Anthony Vannelli
  • JWJames Q. Walker
    James Q. Walker

Abstract
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.

This publication has 6 references indexed in Scilit: