The search functionality is under construction.

Author Search Result

[Author] Yoshiyasu MIMASA(1hit)

1-1hit
  • A Graph Bisection Algorithm Based on Subgraph Migration

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

     
    PAPER

      Vol:
    E77-A No:12
      Page(s):
    2039-2044

    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.