ALGORITHMS FOR PARTITIONING A GRAPH

Abstract

The k-way graph partitioning problem is considered with two efficient heuristic procedures. Algorithms ''local extreme exchange'' (LEE) and ''overall extreme exchange'' (GEE) are presented by modifying Kernighan-Lin's two way uniform partitioning method. In algorithm LEE, a node which maximizes the reduced cost is selected and exchanged with a node in another cluster such that the gain from the exchange with the selected node is maximized. The computational time efficiency of LEE is verified to be excellent compared to Kernighan-Lin's method. Algorithm OEE which considers a node pair that maximizes the reduced exchange cost is illustrated to be superior to the Kernighan-Lin's method. The time requirement of the proposed algorithm is also shown to be smaller than that of Kernighan-Lin's procedure.