| Presentation | 1994/1/26 Minimum Cost Graph Bisection Based on Subgraph Migration Yoshiyasu Mimasa, Kazunori Isomoto, Shin'ichi Wakabayashi, Tetsushi Koide, norika Yosida, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The graph bisection problem is widely used in several applications,such as VLSI layout design.This problem is NP-hard, and hence several heuristic algorithms have been proposed.However, those algorithms are iterative improvment algorithms,in which the current solution is iteratively improved by moving one vertex from one side to other,or exchanging a pair of two vertices.Therefore, those algorithms tend to fall into a local optimum.In this paper, to overcome this problem,we present a heuristic algorithm based on subgraph migration,and show experimental results.Furthermore,to handle large scale data in a short computation time,we extend the proposed algorithm to a parallel algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | minimum cost graph bisection / subgraph migration / heuristic algorithm / parallel algorithm |
| Paper # | COMP93-72 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1994/1/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Minimum Cost Graph Bisection Based on Subgraph Migration |
| Sub Title (in English) | |
| Keyword(1) | minimum cost graph bisection |
| Keyword(2) | subgraph migration |
| Keyword(3) | heuristic algorithm |
| Keyword(4) | parallel algorithm |
| 1st Author's Name | Yoshiyasu Mimasa |
| 1st Author's Affiliation | Faculty of Engineering,Hiroshima University() |
| 2nd Author's Name | Kazunori Isomoto |
| 2nd Author's Affiliation | Technical Research Center,MAZDA Corporation |
| 3rd Author's Name | Shin'ichi Wakabayashi |
| 3rd Author's Affiliation | Faculty of Engineering,Hiroshima University |
| 4th Author's Name | Tetsushi Koide |
| 4th Author's Affiliation | Faculty of Engineering,Hiroshima University |
| 5th Author's Name | norika Yosida |
| 5th Author's Affiliation | Faculty of Engineering,Hiroshima University |
| Date | 1994/1/26 |
| Paper # | COMP93-72 |
| Volume (vol) | vol.93 |
| Number (no) | 438 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |