<i>k</i>-コーダルグラフにおける最適な低競合ショートカット

• Item type: SIG Technical Reports(1)
• 公開日: 2019-01-22
• タイトル: <i>k</i>-コーダルグラフにおける最適な低競合ショートカット
• タイトル / 言語: en
• タイトル: Optimal Low-Congestion Shortcuts for <i>k</i>-Chordal Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者所属: 熊本大学大学院先端科学研究部
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者名: 北川, 大貴; 北村, 直暉; 大館, 陽太; 泉, 泰介
• 著者名(英): Hirotaka, Kitagawa; Naoki, Kitamura; Yota, Otachi; Taisuke, Izumi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿は，CONGEST モデル上のの分散アルゴリズム設計における重要な基本手法の一つである，低競合ショートカットを取り扱う．特に，入力グラフを k - コーダルグラフとした場合，良い低競合ショートカットが存在し，かつ 1 ラウンドでそれを (分散的に) 構成できることを示す．具体的には，任意の n 頂点 k - コーダルグラフに対して，クオリティ O (kD) の低競合ショートカットの構成アルゴリズムを提案する （D はグラフの直径)．この結果は，k があまり大きくない場合，k - コーダルグラフは一般のグラフにおける低競合ショートカットのクオリティの下界 Ω (√n + D) よりも大幅に良いショートカットを持つことを意味している．また，k ≤ D かつ kD ≤ √n の条件のもとで，提案アルゴリズムが最適であること，すなわち低競合ショートカットのクオリティが Ω (kD) となるインスタンスが存在することも示す．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-171, 号 11, p. 1-7, 発行日 2019-01-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会