
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Graph Bisection Algorithm Based on Subgraph Migration
Kazunori ISOMOTO Yoshiyasu MIMASA Shin'ichi WAKABAYASHI Tetsushi KOIDE Noriyoshi YOSHIDA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E77A
No.12
pp.20392044 Publication Date: 1994/12/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms) Category: Keyword: graph partitioning, heuristic algorithm, KernighanLin algorithm, FiducciaMattheyses algorithm, subgraph migration,
Full Text: PDF(576.1KB)>>
Summary:
The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NPhard, and hence several heuristic algorithms have been proposed. Among them, the KernighanLin algorithm and the FiducciaMattheyses 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 KernighanLin and FiducciaMattheyses algorithms.

