制限されたグラフ族に対する最小全域木問題のbroadcast-CONGESTモデルにおける計算時間複雑性

• Item type: SIG Technical Reports(1)
• 公開日: 2022-05-12
• タイトル: 制限されたグラフ族に対する最小全域木問題のbroadcast-CONGESTモデルにおける計算時間複雑性
• タイトル / 言語: en
• タイトル: On Time Complexity of Distributed Minimum Spanning Tree Construction in the broadcast-CONGEST model for Restricted Graph Classes
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: 重清, 成海; 増澤, 利光; 泉, 泰介
• 著者名(英): Narumi, Shigekiyo; Toshimitsu, Masuzawa; Taisuke, Izumi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: broadcast-CONGEST は，分散グラフアルゴリズムの標準的な計算モデルである CONGEST の変種であり，各ラウンドにおいて隣接頂点へと同一のメッセージのみを送信可能であるという制約が課されている．本稿では，broadcast-CONGEST モデルにおける制限されたグラフ族，特に平面的グラフに着目した最小全域木問題の計算時間下界を与える．通常の CONGEST モデルでは一般のグラフにおいては Ω˜ (√n + D) ラウンドの計算時間下界が必要であることが知られている一方で，平面的グラフに対しては Ω˜ (D) 時間で最小全域木を構成することが可能である (D は入力グラフの直径)．本稿では，broadcast-CONGEST モデル上での平面的グラフにおける最小全域木問題の計算時間下界が，一般のグラフと同等の Ω˜ (√n + D) ラウンドを必要とすることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Broadcast-CONGEST is a variant of CONGEST, the standard computational model for distributed graph algorithms, with the restriction that only a common message can be sent to all neighbors in each round. We give the lower bound on the minimum spanning tree problem for restricted graph classes in the broadcast-CONGEST model. While planar graphs admit an efficient MST algorithm running in Ω˜ (D) rounds in the standard CONGEST model, it does not hold in the broadcast-CONGEST model. We show that the minimum spanning tree problem for planar graphs in the broadcast-CONGEST model is as expensive as the general case, which exhibits the lower bound of Ω˜ (√n + D) rounds.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-188, 号 7, p. 1-6, 発行日 2022-05-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会