| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2022-06-09 17:40 一般化ムーアグラフ探索アルゴリズムの高速化 ○平山 拓・右田剛史・高橋規一（岡山大）  NLP2022-11 CCS2022-11 |
|
| 抄録 | （和） | データセンタにおける計算機ネットワークは無向正則グラフでモデル化され，その平均頂点間距離はデータ通信の遅延と密接な関係をもつ．したがって，平均頂点間距離の短い無向正則グラフを探索することは，低遅延ネットワークを実現するための重要な課題である．一方，平均頂点間距離が理論的下界と一致する無向正則グラフは一般化ムーアグラフとよばれ，グラフ理論の分野で古くから研究されている．しかし，一般化ムーアグラフが存在するための頂点数と次数に関する条件は解明されておらず，また，存在を判定するための高速なアルゴリズムも知られていない．本報告では，一般化ムーアグラフを深さ優先で探索する既存のアルゴリズムの修正版を提案し，その有効性を実験的に検証する．提案法には探索する辺の削減や探索順の変更など，探索効率化のための新たなアイデアが導入されている．これらのアイデアが実際に有効であることを実験的に示す． |
| （英） | 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 / / / / / | |
| 文献情報 | 信学技報, vol. 122, no. 65, NLP2022-11, pp. 52-57, 2022年6月. | |
| 資料番号 | NLP2022-11 | |
| 発行日 | 2022-06-02 (NLP, CCS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NLP2022-11 CCS2022-11 |
|
| 研究会情報 | |
| 研究会 | CCS NLP |
| 開催期間 | 2022-06-09 - 2022-06-10 |
| 開催地（和） | 大阪大学 豊中キャンパス シグマホール |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | NLP |
| 会議コード | 2022-06-CCS-NLP |
| 本文の言語 | 日本語 |
| タイトル（和） | 一般化ムーアグラフ探索アルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Speeding up an algorithm for searching generalized Moore graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ理論 / graph theory |
| キーワード(2)（和/英） | 一般化ムーアグラフ / generalized Moore graph |
| キーワード(3)（和/英） | 平均頂点間距離 / average shortest path length |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 平山 拓 / Taku Hirayama / ヒラヤマ タク |
| 第1著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 右田 剛史 / Tsuyoshi Migita / ミギタ ツヨシ |
| 第2著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 高橋 規一 / Norikazu Takahashi / タカハシ ノリカズ |
| 第3著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-06-09 17:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NLP |
| 資料番号 | NLP2022-11, CCS2022-11 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.65(NLP), no.66(CCS) |
| ページ範囲 | pp.52-57 |
| ページ数 | 6 |
| 発行日 | 2022-06-02 (NLP, CCS) |
[研究会発表申込システムのトップページに戻る]