| 講演名 | 2024-03-14 平均頂点間距離が最小の正則グラフを探索するアルゴリズムの並列化 平山 拓(岡山大), 右田 剛史(岡山大), 高橋 規一(岡山大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | データセンタにおける計算機ネットワークは正則グラフでモデル化され，その平均頂点間距離はデータ通信の遅延と密接な関係をもつ．したがって，平均頂点間距離の短い正則グラフを求めることは，低遅延ネットワークを実現するための重要な課題である．平均頂点間距離が理論的下界に等しい正則グラフは一般化ムーアグラフとよばれ，その特徴や存在条件に関する理論解析が古くから行われてきた．また，一般化ムーアグラフを探索するアルゴリズムに関する研究も行われてきた．本報告では，指定の頂点数と次数の下で平均頂点間距離を最小にする正則グラフを深さ優先で探索するアルゴリズムを提案し，その有効性を実験的に検証する．提案するアルゴリズムは，一般化ムーアグラフを探索する既存のアルゴリズムを本研究の目的に合わせて修正し，さらに探索の効率化のために枝刈りや並列化を導入したものである． |
| 抄録(英) | Computer networks in data centers are modeled as 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 a regular graph with a short ASPL is an important issue for designing low-latency networks. A regular graph whose ASPL is equal to a theoretical lower bound is called a generalized Moore graph. Theoretical analysis on the properties of generalized Moore graphs and conditions for their existence have been conducted for many decades. Also, studies on algorithms to search for generalized Moore graphs have been done. In this report, we propose a depth-first search algorithm to find regular graphs that minimizes the ASPL under a specified number of vertices and degree, and verify its effectiveness through experiments. The proposed algorithm is derived by modifying an existing algorithm for searching generalized Moore graphs to suit the purpose of this study, and introducing pruning and parallelization to further improve search efficiency. |
| キーワード(和) | グラフ理論 / 一般化ムーアグラフ / 平均頂点間距離 / 深さ優先探索 / 枝刈り |
| キーワード(英) | graph theory / generalized Moore graph / average shortest path length / depth-first search / pruning |
| 資料番号 | MSS2023-89,NLP2023-141 |
| 発行日 | 2024-03-06 (MSS, NLP) |
| 研究会情報 | |
| 研究会 | NLP / MSS |
|---|---|
| 開催期間 | 2024/3/13(から2日開催) |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | MSS，NLP，一般，およびWIP（MSSのみ） |
| テーマ（英） | MSS, NLP, etc. |
| 委員長氏名（和） | 鳥飼 弘幸(法政大) / 山口 真悟(山口大) |
| 委員長氏名（英） | Hiroyuki Torikai(Hosei Univ.) / Shingo Yamaguchi(Yamaguchi Univ.) |
| 副委員長氏名（和） | 丹治 裕一(香川大) / 宮本 俊幸(阪工大) |
| 副委員長氏名（英） | Yuichi Tanji(Kagawa Univ.) / Toshiyuki Miyamoto(Osaka Inst. of Tech.) |
| 幹事氏名（和） | 伊藤 大輔(岐阜大) / 青森 久(中京大) / 林 直樹(阪大) / 劉 健全(NEC) |
| 幹事氏名（英） | Daisuke Ito(Gifu Univ.) / Hisashi Aomori(Chukyo Univ.) / Naoki Hayashi(Osaka Univ.) / Jianquan Liui(NEC) |
| 幹事補佐氏名（和） | 山仲 芳和(宇都宮大) / 井岡 恵理(芝浦工大) / 白井 匡人(島根大) |
| 幹事補佐氏名（英） | Yoshikazu Yamanaka(Utsunomiya Univ.) / Eri Ioka(Shibaura Inst. of Tech.) / Masato Shirai(Shimane Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Nonlinear Problems / Technical Committee on Mathematical Systems Science and its Applications |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 平均頂点間距離が最小の正則グラフを探索するアルゴリズムの並列化 |
| サブタイトル（和） | |
| タイトル（英） | Parallelization of a Search Algorithm for Regular Graphs with Minimum Average Shortest Path Length |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ理論 / graph theory |
| キーワード(2)（和/英） | 一般化ムーアグラフ / generalized Moore graph |
| キーワード(3)（和/英） | 平均頂点間距離 / average shortest path length |
| キーワード(4)（和/英） | 深さ優先探索 / depth-first search |
| キーワード(5)（和/英） | 枝刈り / pruning |
| 第 1 著者 氏名（和/英） | 平山 拓 / Taku Hirayama |
| 第 1 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 2 著者 氏名（和/英） | 右田 剛史 / Tsuyoshi Migita |
| 第 2 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 3 著者 氏名（和/英） | 高橋 規一 / Norikazu Takahashi |
| 第 3 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 発表年月日 | 2024-03-14 |
| 資料番号 | MSS2023-89,NLP2023-141 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | MSS-427,NLP-428 |
| ページ範囲 | pp.87-92(MSS), pp.87-92(NLP), |
| ページ数 | 6 |
| 発行日 | 2024-03-06 (MSS, NLP) |