A Graph Bisection Algorithm Based on Subgraph Migration

Kazunori ISOMOTO  Yoshiyasu MIMASA  Shin'ichi WAKABAYASHI  Tetsushi KOIDE  Noriyoshi YOSHIDA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.12   pp.2039-2044
Publication Date: 1994/12/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
graph partitioning,  heuristic algorithm,  Kernighan-Lin algorithm,  Fiduccia-Mattheyses algorithm,  subgraph migration,  

Full Text: PDF>>
Buy this Article

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.