| Presentation | 1996/12/14 A Binary 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) | In this paper, we present a neural network algorithm using binary neurons for a graph two-partitioning problem. For a given graph G(V, E), the goal of this NP-hard problem is to find a partition of vertices in V into two groups such that not only the sum of vertex-weights in each group is within the upper bound, but also the sum of edge-weights between groups is minimized. We formulate a new energy function and introduce a shaking term in the motion equation in order to improve the solution quality. We compare the performance of the neural network with two existing typical algorithms through simulations in unweighted and weighted random graphs. The results show that the neural network is comparable with existing algorithms for vertex-unweighted graphs in terms of the solution quality, and that it is much better for vertex-weighted graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | neural network / graph two-partitioning problem / NP hard problem / shaking term |
| Paper # | NC96-64 |
| Date of Issue |
| Conference Information | |
| Committee | NC |
|---|---|
| Conference Date | 1996/12/14(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 Binary Neural Network Algorithm for the Graph Partitioning Problem |
| Sub Title (in English) | |
| Keyword(1) | neural network |
| Keyword(2) | graph two-partitioning problem |
| Keyword(3) | NP hard problem |
| Keyword(4) | shaking term |
| 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/12/14 |
| Paper # | NC96-64 |
| Volume (vol) | vol.96 |
| Number (no) | 430 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |