| 講演名 | 2022-06-09 一般化ムーアグラフ探索アルゴリズムの高速化 平山 拓(岡山大), 右田 剛史(岡山大), 高橋 規一(岡山大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | データセンタにおける計算機ネットワークは無向正則グラフでモデル化され，その平均頂点間距離はデータ通信の遅延と密接な関係をもつ．したがって，平均頂点間距離の短い無向正則グラフを探索することは，低遅延ネットワークを実現するための重要な課題である．一方，平均頂点間距離が理論的下界と一致する無向正則グラフは一般化ムーアグラフとよばれ，グラフ理論の分野で古くから研究されている．しかし，一般化ムーアグラフが存在するための頂点数と次数に関する条件は解明されておらず，また，存在を判定するための高速なアルゴリズムも知られていない．本報告では，一般化ムーアグラフを深さ優先で探索する既存のアルゴリズムの修正版を提案し，その有効性を実験的に検証する．提案法には探索する辺の削減や探索順の変更など，探索効率化のための新たなアイデアが導入されている．これらのアイデアが実際に有効であることを実験的に示す． |
| 抄録(英) | 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. |
| キーワード(和) | グラフ理論 / 一般化ムーアグラフ / 平均頂点間距離 |
| キーワード(英) | graph theory / generalized Moore graph / average shortest path length |
| 資料番号 | NLP2022-11,CCS2022-11 |
| 発行日 | 2022-06-02 (NLP, CCS) |
| 研究会情報 | |
| 研究会 | CCS / NLP |
|---|---|
| 開催期間 | 2022/6/9(から2日開催) |
| 開催地（和） | 大阪大学 豊中キャンパス シグマホール |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 赤井 恵(北大) / 常田 明夫(熊本大) |
| 委員長氏名（英） | Megumi Akai(Hokkaido Univ.) / Akio Tsuneda(Kumamoto Univ.) |
| 副委員長氏名（和） | 会田 雅樹(都立大) / 中野 秀洋(東京都市大) / 鳥飼 弘幸(法政大) |
| 副委員長氏名（英） | Masaki Aida(TMU) / Hidehiro Nakano(Tokyo City Univ.) / Hiroyuki Torikai(Hosei Univ.) |
| 幹事氏名（和） | 眞田 耕輔(三重大) / 宮田 純子(芝浦工大) / 吉岡 大三郎(崇城大) / 伊藤 大輔(岐阜大) |
| 幹事氏名（英） | Kosuke Sanada(TDK) / Sumiko Miyata(Shibaura Insti. of Tech.) / Daisaburo Yoshioka(Sojo Univ.) / Daisuke Ito(Gifu Univ.) |
| 幹事補佐氏名（和） | 佐々木 智志(湘南工科大学) / 安東 弘泰(筑波大) / 小林 幹(立正大学) / 安田 裕之(東京大学) / 横井 裕一(長崎大) / 山仲 芳和(宇都宮大) |
| 幹事補佐氏名（英） | 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.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Complex Communication Sciences / Technical Committee on Nonlinear Problems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 一般化ムーアグラフ探索アルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Speeding up an algorithm for searching generalized Moore graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ理論 / graph theory |
| キーワード(2)（和/英） | 一般化ムーアグラフ / generalized Moore graph |
| キーワード(3)（和/英） | 平均頂点間距離 / average shortest path length |
| 第 1 著者 氏名（和/英） | 平山 拓 / Taku Hirayama |
| 第 1 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 2 著者 氏名（和/英） | 右田 剛史 / Tsuyoshi Migita |
| 第 2 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 3 著者 氏名（和/英） | 高橋 規一 / Norikazu Takahashi |
| 第 3 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 発表年月日 | 2022-06-09 |
| 資料番号 | NLP2022-11,CCS2022-11 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | NLP-65,CCS-66 |
| ページ範囲 | pp.52-57(NLP), pp.52-57(CCS), |
| ページ数 | 6 |
| 発行日 | 2022-06-02 (NLP, CCS) |