| Presentation | 1996/7/24 A Neural Network Algorithm for the Graph Partitioning Problem Yasuhiro Tamaki, Nobuo Funabiki, Seishi Nishikawa, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The graph partitioning problem requires to partition the vertices of a given graph into several groups within the specified size so as to minimize the sum of the edge weights between groups. In this paper, we propose a neural network algorithm for the graph two-partitioning problem using the binary neuron model. We introduce the shaking term inthe motion equation in order to improve the solution quality. For the performance evaluation, we applied the proposed algorithm for random graphs to compare the running time and the solution quality with existing algorithms. As for solution quality, our algorithm is nearly equal to the KL algorithm, whereas as for the running time, our algorithm is much faster than the KL algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph partitioning problem / neural network / shaking term / KL algorithm |
| Paper # | NC96-35 |
| Date of Issue |
| Conference Information | |
| Committee | NC |
|---|---|
| Conference Date | 1996/7/24(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 | Neurocomputing (NC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Neural Network Algorithm for the Graph Partitioning Problem |
| Sub Title (in English) | |
| Keyword(1) | graph partitioning problem |
| Keyword(2) | neural network |
| Keyword(3) | shaking term |
| Keyword(4) | KL algorithm |
| 1st Author's Name | Yasuhiro Tamaki |
| 1st Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science,Osaka University() |
| 2nd Author's Name | Nobuo Funabiki |
| 2nd Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science,Osaka University |
| 3rd Author's Name | Seishi Nishikawa |
| 3rd Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science,Osaka University |
| Date | 1996/7/24 |
| Paper # | NC96-35 |
| Volume (vol) | vol.96 |
| Number (no) | 178 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |