| Presentation | 2022-06-09 Speeding up an algorithm for searching generalized Moore graphs Taku Hirayama, Tsuyoshi Migita, Norikazu Takahashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Computer networks in data centers are modeled as undirected regular graphs, and the average shortest path length (ASPL) of such a graph is closely related to data transmission latency in the corresponding computer network. Therefore, finding an undirected regular graph with a short ASPL is an important issue for low-latency network design. Regular graphs whose ASPLs are equal to certain theoretical lower bounds are called generalized Moore graphs, and have been studied in the field of graph theory for many years. However, the conditions on the number of vertices and the degree for a generalized Moore graph to exist have not been clarified, nor is there a fast algorithm for determining its existence. In this report, we propose a modified version of an existing depth-first search algorithm for generalized Moore graphs, and verify its effectiveness experimentally. In the proposed algorithm, new ideas for reducing the number of edges to be searched and changing the order of edge search adaptively are introduced. Experimental results show that these ideas are effective in practice. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph theory / generalized Moore graph / average shortest path length |
| Paper # | NLP2022-11,CCS2022-11 |
| Date of Issue | 2022-06-02 (NLP, CCS) |
| Conference Information | |
| Committee | CCS / NLP |
|---|---|
| Conference Date | 2022/6/9(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Megumi Akai(Hokkaido Univ.) / Akio Tsuneda(Kumamoto Univ.) |
| Vice Chair | Masaki Aida(TMU) / Hidehiro Nakano(Tokyo City Univ.) / Hiroyuki Torikai(Hosei Univ.) |
| Secretary | Masaki Aida(TDK) / Hidehiro Nakano(Shibaura Insti. of Tech.) / Hiroyuki Torikai(Sojo Univ.) |
| Assistant | Tomoyuki Sasaki(Shonan Instit. of Tech.) / Hiroyasu Ando(Tsukuba Univ.) / Miki Kobayashi(Rissho Univ.) / " Hiroyuki YASUDA(The Univ. of Tokyo) / Yuichi Yokoi(Nagasaki Univ.) / Yoshikazu Yamanaka(Utsunomiya Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Complex Communication Sciences / Technical Committee on Nonlinear Problems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Speeding up an algorithm for searching generalized Moore graphs |
| Sub Title (in English) | |
| Keyword(1) | graph theory |
| Keyword(2) | generalized Moore graph |
| Keyword(3) | average shortest path length |
| 1st Author's Name | Taku Hirayama |
| 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 | 2022-06-09 |
| Paper # | NLP2022-11,CCS2022-11 |
| Volume (vol) | vol.122 |
| Number (no) | NLP-65,CCS-66 |
| Page | pp.pp.52-57(NLP), pp.52-57(CCS), |
| #Pages | 6 |
| Date of Issue | 2022-06-02 (NLP, CCS) |