文献

J-GLOBAL ID：202202237979181164   整理番号：22A2080280

一般化ムーアグラフ探索アルゴリズムの高速化

Speeding Up an Algorithm for Searching Generalized Moore Graphs

著者 (3件)： 平山拓 (岡山大 大学院自然科学研究科) ,  右田剛史 (岡山大 大学院自然科学研究科) ,  高橋規一 (岡山大 大学院自然科学研究科)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 122  号： 65(NLP2022 1-25)  ページ： 52-57 (WEB ONLY)  発行年： 2022年06月02日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： データセンタにおける計算機ネットワークは無向正則グラフでモデル化され,その平均頂点間距離はデータ通信の遅延と密接な関係をもつ.したがって,平均頂点間距離の短い無向正則グラフを探索することは,低遅延ネットワークを実現するための重要な課題である.一方,平均頂点間距離が理論的下界と一致する無向正則グラフは一般化ムーアグラフとよばれ,グラフ理論の分野で古くから研究されている.しかし,一般化ムーアグラフが存在するための頂点数と次数に関する条件は解明されておらず,また,存在を判定するための高速なアルゴリズムも知られていない.本報告では,一般化ムーアグラフを深さ優先で探索する既存のアルゴリズムの修正版を提案し,その有効性を実験的に検証する.提案法には探索する辺の削減や探索順の変更など,探索効率化のための新たなアイデアが導入されている.これらのアイデアが実際に有効であることを実験的に示す.(著者抄録)

シソーラス用語： *アルゴリズム ,  *計算機網 ,  *グラフ理論 ,  無向グラフ ,  *遅延特性 ,  遅れ ,  *グラフ ,  情報検索
準シソーラス用語： *Mooreグラフ ,  ネットワーク遅延 ,  正則グラフ ,  設計空間探索 ,  *探索アルゴリズム

分類 (2件)： 計算機網  (JC03000K) ,  グラフ理論基礎  (IA02020S)

引用文献 (12件)：

• A. Singla, C. Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: networking data centers randomly,” Proceedings of 9th USENIX Symposium on Networked Systems Design and Implementation, pp.225-238, 2012.
• M. Koibuchi, H. Matsutani, H. Amano, D. F. Hsu, and H. Casanova, “A case for random shortcut topologies for HPC interconnects,” Proceedings of International Symposium on Computer Architecture, vol.40, no.3, pp.177-188, 2012.
• A. J. Hoffman and R. R. Singleton, “On Moore graphs with diameters 2 and 3”, IBM Journal of Research and Development, vol.4, pp.497-504, 1960.
• H. D. Friedman, “On the impossibility of Certain Moore Graphs”, Journal of Combinatorial Theory, Series B, vol.10, pp.245-252, 1971.
• L. K. Jorgensen, “Nonexistence of certain cubic graphs with small diameters”, Discrete Mathematics, vol.114, pp.265-273, 1993.

タイトルに関連する用語 (4件)： 一般化 ,  グラフ ,  探索アルゴリズム ,  高速化