Article ID: | iaor19881118 |
Country: | United States |
Volume: | 1 |
Issue: | 3 |
Start Page Number: | 299 |
End Page Number: | 305 |
Publication Date: | Aug 1988 |
Journal: | SIAM Journal On Discrete Mathematics |
Authors: | Barnes Earl R., Vannelli Anthony, Walker James Q. |
Keywords: | heuristics, graphs |
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 the authors describe a fast procedure for determining sets of nodes to interchange in order to improve an initial partition.