動的Steiner木生成問題のための分散アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1999-11-18
• タイトル: 動的Steiner木生成問題のための分散アルゴリズム
• タイトル / 言語: en
• タイトル: Distributed Algorithms for Dynamic Steiner Tree Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院工学研究科
• 著者所属: 北海道大学大型計算機センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Hokkaido University Computing Center
• 著者名: 塚田, 慎; 高井, 昌彰
• 著者名(英): Makoto, Tsukada; Yoshiaki, Takai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マルチキャストサービスの発展により、異なるマルチキャストパスが同一ネットワーク上に共存する状況も珍しくなくなっている。異なるマルチキャストパスの各々のアプリケーションにとって、通信のオーバーヘッドを最小にする経路を設定することは重要である。この問題は最小Steiner木生成問題を分散環境で複数同時生成することに相当する。本論文では、共通の制約で複数の最小Steiner木の近似解を同時生成する分散アルゴリズムについて論じる。また、マルチキャストメンバーノードが動的に変更しうる動的Steiner木生成問題に関する分散アルゴリズムについても論じる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In crease of multicast services brings the situation that different multicast paths coexist in the same computer network. It is important to arrange the multicast paths to minimize the communication overhead for each application on the different multicast paths. This problem is a minimum Steiner tree problem in the distributed environment. In this paper we discuss a distributed algorithm that generates multiple quasi-minimum Steiner trees at the same time under the common constraint. We also discuss a distributed algorithm for a dynamic Steiner tree problem in which multicast member nodes can be dynamically changed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10116224
• 書誌情報: 情報処理学会研究報告マルチメディア通信と分散処理（DPS）; 巻 1999, 号 94(1999-DPS-095), p. 55-60, 発行日 1999-11-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会