被覆容量/要求回数付き部分頂点被覆問題の2倍近似解法(アルゴリズム理論)
スポンサーリンク
概要
- 論文の詳細を見る
グラフの頂点被覆問題はよく知られたNP-困難な組合せ最適化問題である.ここでは,無向グラフが与えられたとき,すべての辺について少なくともどちらか一方の端点を含むような頂点部分集合のうち,含まれる頂点の重みの合計が最小であるものが求められる.これまで同問題には,各頂点が被覆できる辺数に制限を加えたり,ある決められた割合の辺数だけ被覆することを要求するなどの一般化が個々に考えられてきた.本論文では辺や頂点に関するこれらの被覆条件を併せ持つ一般化問題を新たに導入し,劣モジュラ被覆アルゴリズムを拡張することで,この問題に対して近似率2が多項式時間で保証できることを示す.
- 社団法人電子情報通信学会の論文
- 2004-11-01
著者
関連論文
- 連結頂点被覆問題およびtree cover問題に対する2倍近似並列アルゴリズム
- データ構造とアルゴリズム, 杉原厚吉(著), "データ構造とアルゴリズム",共立出版(2001-12);A5判, 定価(本体2,200円+税)
- d-claw freeグラフ上の独立集合問題に対する局所探索法について
- 2値重み集合被覆問題に対する貪欲法の改良について
- 重みが1と2の集合被覆問題に対する貪欲法の改良
- 劣モジュラ被覆問題の近似について
- 最小コスト木状被覆問題の2倍近似アルゴリズム
- 重みつき集合充填問題に対する局所改善法について
- 集合多重被覆問題に対する貪欲法の改良
- 被覆容量/要求回数付き部分頂点被覆問題の2倍近似解法(アルゴリズム理論)
- A 2-Approximation Algorithm for Capacitated Partial Vertex Cover with Demands〔和文〕
- COMP2000-15 独立/連結な辺支配集合問題の近似可能性について
- 辺支配集合問題の2倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)