| Presentation | 1996/11/29 A Neural Network Algorithm for the Minimum Maximal Matching Problem Shunji Umetani, Nobuo Funabiki, Seishi Nishikawa, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For a given graph G(V,E), a subset M of E is called a matching of G if no pair of edges in M is adjacent to each other. In this paper, we present a neural network parallel algorithm for the minimum maximal matching problem. This NP-complete problem requires to find a maximal matching composed of the least number of edges in G. The neural network consists of N × N binary neurons for the N-vertex graph problem. In order to improve the solution quality, we present a heuristic term into the motion equation for diagonal neurons which represent the exclusion of vertices from the matching. We verify the performance through simulations using random graph, where our neural network finds better solutions than the greedy algorithm and the simulated annealing. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Minimum Maximal Matching / Neural Network / Binary Neuron / NP-complete / Graph |
| Paper # | NC96-52 |
| Date of Issue |
| Conference Information | |
| Committee | NC |
|---|---|
| Conference Date | 1996/11/29(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 Minimum Maximal Matching Problem |
| Sub Title (in English) | |
| Keyword(1) | Minimum Maximal Matching |
| Keyword(2) | Neural Network |
| Keyword(3) | Binary Neuron |
| Keyword(4) | NP-complete |
| Keyword(5) | Graph |
| 1st Author's Name | Shunji Umetani |
| 1st Author's Affiliation | Division of Informatics and Mathematical Science, Graduated School of Engineering Science, Osaka University() |
| 2nd Author's Name | Nobuo Funabiki |
| 2nd Author's Affiliation | Division of Informatics and Mathematical Science, Graduated School of Engineering Science, Osaka University |
| 3rd Author's Name | Seishi Nishikawa |
| 3rd Author's Affiliation | Division of Informatics and Mathematical Science, Graduated School of Engineering Science, Osaka University |
| Date | 1996/11/29 |
| Paper # | NC96-52 |
| Volume (vol) | vol.96 |
| Number (no) | 393 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |