連結頂点被覆問題およびtree cover問題に対する2倍近似並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
連結頂点被覆問題とtree cover問題は,それぞれ,頂点被覆問題と辺支配集合問題に連結性という制約が付加された問題であり,同様の近似性を有するNP完全な問題である,これらの問題に対して,すでにいくつかの2倍近似の逐次アルゴリズムが知られているが,NC(ならびにRNC)アルゴリズムは知られていない.そこで,本稿では,連結頂点被覆問題およびtree cover問題に対する2倍近似のNC(ならびにRNC)アルゴリズムを提案する.入力グラフの頂点数n,辺数m,最大次数△とすると,このNCアルゴリズムは,EREW-PRAM上でO(△^2(m+n)/log n)個のプロセッサを用いてO(log^2 n)時間で並列に実行でき,RNCアルゴリズムは,CRCW-PRAM上でO(m+n)個のプロセッサを用いて期待値O(log n)の時間で並列に実行できる.
- 2003-01-17
著者
関連論文
- 連結頂点被覆問題および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倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)