トーラスに規則的に辺を追加した直径および平均パス長最小のグラフ

• Item type: SIG Technical Reports(1)
• 公開日: 2016-08-01
• タイトル: トーラスに規則的に辺を追加した直径および平均パス長最小のグラフ
• タイトル / 言語: en
• タイトル: Regularly Edge-added Torus Graphs with the Minimum Diameter and the Minimum Average Shortest Path Length
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ネットワーク・グラフ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪府立大学大学院理学系研究科
• 著者所属: 大阪府立大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science Osaka Prefecture University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering Osaka Prefecture University
• 著者名: 小林, 寛之; 藤本, 典幸
• 著者名(英): Hiroyuki, Kobayashi; Noriyuki, Fujimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年のマルチコアプロセッサがもつコア数は年々増加しており，それらすべてを相互に接続することは現実的ではない．そこでコア間を接続するネットワークのトポロジに関する様々な問題が研究されている．そのような問題のひとつに，与えられた頂点数と最大次数を持つすべてのグラフの中で直径および平均パス長が最小のグラフを見つける問題 (Ordeｒ/Degree問題） がある．本論文では与えられた頂点数と最大次数を満たす範囲でトーラスの各頂点に辺を規則的に追加し，そのようなグラフの中で直径および平均パス長が最小となるものをすべて列挙するアルゴリズムを提案する．またそれを用いて発見した Order/Degree 問題の最適解となるグラフを報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is not realistic to connect all of cores in a multicore-processor each other because current multicore-processors have many cores. Therefore there are many studies about network topologies to connect cores. The order/degree problem is one of the tackled problems. It finds graphs with the minimum diameter and the minimum average shortest path length (ASPL) over all graphs for a given number n of vertices and a given degree deg. We present an algorithm to enumerate all of graphs with the minimum diameter and the minimum ASPL over all graphs such that each vertex of torus with n vertices is added edges regularly within degree deg. Also we report optimal graphs for the order/degree problem found by our algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告システム・アーキテクチャ（ARC）; 巻 2016-ARC-221, 号 45, p. 1-6, 発行日 2016-08-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8574
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会