スタイナーネットワーク問題に対する近似アルゴリズムの実験的性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2001-03-12
• タイトル: スタイナーネットワーク問題に対する近似アルゴリズムの実験的性能評価
• タイトル / 言語: en
• タイトル: Practical Evaluation of Approximation Algorithms for the Steiner Network Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学大学院理工学研究科情報工学専攻
• 著者所属: 中央大学大学院理工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者名: 八巻, 満隆; 浅野, 孝夫
• 著者名(英): Yamaki, Mitsutaka; Asano, Takao
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: スタイナーネットワーク問題はネットワーク設計やネットワークルーティングと密接に関係する問題で，実用上しばしば起こる問題である．本論文では，スタイナーネットワーク問題の特殊版であるスタイナー木問題に対して，最近提案された精度保証付きの近似アルゴリズムを実装し，実装上の工夫を施したアルゴリズムとともに計算機実験を行い，それらの実験的性能評価を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The steiner network problem is closely related to network design and network routing in real world applications. In this paper, we implement several recently proposed approximation algorithms for the steiner tree problem on undirected graphs and directed graphs including our improvements, and try to evaluate the practical performances of these algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 25(2000-AL-077), p. 73-80, 発行日 2001-03-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会