| Presentation | 2020-05-15 A Genetic Algorithm for Minimizing Average Shortest Path Length of Regular Graphs Reiji Hayashi, Tsuyoshi Migita, Norikazu Takahashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For the problem of finding a regular graph with given order and degree that minimizes the average shortest path length, we propose a novel genetic-algorithm-based method for finding an approximate solution. Since the search space consists only of regular graphs, existing genetic algorithms cannot be applied directly. We propose in this report a new crossover technique and a new mutation technique that guarantee regularity of graphs. We also evaluate the effectiveness of the proposed method experimentally. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | regular graph / average shortest path length / genetic algorithm / Havel-Hakimi theorem |
| Paper # | NLP2020-3 |
| Date of Issue | 2020-05-08 (NLP) |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2020/5/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Yamaguchi University (Tokiwa campus) |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroaki Kurokawa(Tokyo Univ. of Tech.) |
| Vice Chair | Kiyohisa Natsume(Kyushu Inst. of Tech.) |
| Secretary | Kiyohisa Natsume(Nippon Inst. of Tech.) |
| Assistant | Yutaka Shimada(Saitama Univ.) / Toshikaza Samura(Yamaguchi Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Nonlinear Problems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Genetic Algorithm for Minimizing Average Shortest Path Length of Regular Graphs |
| Sub Title (in English) | |
| Keyword(1) | regular graph |
| Keyword(2) | average shortest path length |
| Keyword(3) | genetic algorithm |
| Keyword(4) | Havel-Hakimi theorem |
| 1st Author's Name | Reiji Hayashi |
| 1st Author's Affiliation | Okayama University(Okayama Univ.) |
| 2nd Author's Name | Tsuyoshi Migita |
| 2nd Author's Affiliation | Okayama University(Okayama Univ.) |
| 3rd Author's Name | Norikazu Takahashi |
| 3rd Author's Affiliation | Okayama University(Okayama Univ.) |
| Date | 2020-05-15 |
| Paper # | NLP2020-3 |
| Volume (vol) | vol.120 |
| Number (no) | NLP-26 |
| Page | pp.pp.11-16(NLP), |
| #Pages | 6 |
| Date of Issue | 2020-05-08 (NLP) |