最小重みの有向部分木アルゴリズムの実験的性能評価

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では,有向閉路を持たない連結な有向グラフ上の各枝に任意の実数重みが与えられたとき,最小重みの根付き有向部分木を求める問題を考える.この問題はV. V. Rao and R. Sridharan, "Minimum-weight rooted not-necessarily-spanning arborescence problem." Networks, vol. 39(2), pp. 77-87 (2002)で,初めて提案された.上記の論文では,その問題がNP困難であることを証明した.さらに,この問題に適したラグランジュ緩和法を提案し,比較的良好な計算実験の結果を示した.しかし,そこでは入力となるグラフの生成手法を明確に示しておらず,さらに非常に小さなグラフサイズを入力としていた.また,各枝に付されている重みも偏ったものであった.本論文では,上記の論文の手法を実装し,比較的大きなグラフサイズ,および広範囲にわたる各枝の重みを入力として,その手法の有効性を検討する.

• 2011-08-30

著者

• 千葉 英史

  法政大学理工学部経営システム工学科

• 安部 友輔

  法政大学工学研究科

関連論文

• A-006 マルチスロット活動選択問題(モデル・アルゴリズム・プログラミング,一般論文)
• A-031 最大利益根付木問題に対するヒューリスティックアルゴリズム(A分野:モデル・アルゴリズム・プログラミング,一般論文)
• 最小重みの有向部分木アルゴリズムの実験的性能評価
• 最小重みの有向部分木アルゴリズムの実験的性能評価
• A-005 根付き部分木の総利益最大化(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
• A-032 最小重みの有向部分木アルゴリズムの実験的性能評価(アルゴリズム・コンピュテーション(3),A分野:モデル・アルゴリズム・プログラミング)

スポンサーリンク