木における賞金収集辺支配集合問題に対する多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,辺支配集合問題を一般化した問題である賞金収集辺支配集合問題を扱う.賞金収集辺支配集合問題では,通常の辺支配集合問題とは異なり,全ての辺を支配することを強制されないかわりに,支配することができなかった辺に対しては罰則を払う必要がある.この問題はNP困難であることが知られており,Parekhによって8/3-近似アルゴリズムが提案されている.しかし,我々の知る限りでは,多項式時間でこの問題が解くことのできるグラフのクラスは知られていない.本論文では,木における賞金収集辺支配集合問題が多項式時間で解けることを示す.
- 2010-06-18
著者
関連論文
- 木における消防士問題に対する近似アルゴリズムの改良 (コンピュテーション)
- 動的ネットワーク上の最速フロー問題と有向グラフ上の有向木問題の研究 : 都市における避難計画に対する理論的アプローチ(研究会推薦博士論文速報)
- 木における消防士問題に対する近似アルゴリズムの改良
- 木における賞金収集辺支配集合問題に対する多項式時間アルゴリズム
- 動的ネットワークフロー(最先端を目指す若手研究者達)
- 5336 経路障害発生時の集団経路探索行動における情報共有の有効性に関する理論的研究(経路探索,建築計画I)
- グラフにおける辺-辺隣接行列の完全ユニモジュラ性に対する必要十分条件
- グラフにおける辺-辺隣接行列の完全ユニモジュラ性に対する必要十分条件 (コンピュテーション)
- グラフにおける辺-辺隣接行列の完全ユニモジュラ性に対する必要十分条件