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

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1988-08, Vol.1 (3), p.299-305
Main Authors: Barnes, Earl R., Vannelli, Anthony, Walker, James Q.
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Heuristic
Linear programming
Research centers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0895-4801
1095-7146
DOI:10.1137/0401030