分散コンピューティング制御効率化のための平方分割手法による動的グラフにおける最小全域木クエリ処理

• Item type: SIG Technical Reports(1)
• 公開日: 2016-06-17
• タイトル: 分散コンピューティング制御効率化のための平方分割手法による動的グラフにおける最小全域木クエリ処理
• タイトル / 言語: en
• タイトル: MST Query on Dynamic Graph with Square-Root-Decomposition for Optimization for Controlling Distributed Computing
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者名: 山崎, 一明
• 著者名(英): Kazuaki, Yamazaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: モバイル機器での分散コンピューティング制御はデータ転送に無線通信を利用するが，環境の影響を受けコストや可用性が変化する無線通信においては，最適なネットワークも変化する．最適なネットワークとはグラフ理論における最小全域木に対応する．本研究は最小全域木に基づいてネットワークを再構築することで通信コストを最小化できることを示し，そのための効率的な手法を提案することを目的とする．グラフ G=(V,E) の最小全域木を求める Prim や Kruskal のアルゴリズムがあるが，どちらも O(
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Distributed computing on mobile entities uses wireless communication for data transportation. Costs and availability of wireless communication changes affected by surroundings, thus optimal network (corresponds a MST) also change. Dynamic network can be modeled in dynamic graphs. This paper proposes a method for calculating Minimum Spanning Tree (MST) on dynamic graphs efficiently. The method is based on square-root-decomposition on tree nodes and dividing edge set into several sets according vertex dividing. Then, number of edges that candidate for MST is decreased and we can search edge in shorter time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-158, 号 9, p. 1-8, 発行日 2016-06-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会