翻訳と辞書
Words near each other
・ 最小費用の原理
・ 最小距離復号
・ 最小軌間鉄道
・ 最小量
・ 最小間隔(間隙)
・ 最小阻止濃度
・ 最小限
・ 最小限度
・ 最小電流勾配
・ 最小面積
最小頂点被覆問題
・ 最小麻酔濃度
・ 最少
・ 最少(小)有効量
・ 最少(小)量
・ 最少則
・ 最少培地
・ 最少律
・ 最少必須培地
・ 最少必須培養液


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

最小頂点被覆問題 : ウィキペディア日本語版
最小頂点被覆問題[さいしょうちょうてんひふくもんだい]
最小頂点被覆問題(さいしょうちょうてんひふくもんだい)は、計算複雑性理論におけるNP困難な問題の一つ。
問題: グラフ ''G''(''V'', ''E'') の各枝 ''e'' について端点のいずれか少なくとも一方が、''V''′ に含まれるような ''V'' の部分集合 ''V''′ のうち、|''V''′| が最小になるものを求めよ
この問題の最適解を求めるのは、NP困難なため、決定性の多項式時間アルゴリズムは存在しないと考えられている。近似アルゴリズムに関して言えば、近似度2の貪欲アルゴリズムが存在することが知られているが、任意の ε > 0 について、近似度 2 - ε の近似度を達成するアルゴリズムも存在しないだろうと考えられている。2005年現在の最良の近似度の下限は、10\sqrt-21 (>1.36) である。
== 関連項目 ==

* 頂点被覆
* 最適化問題
* 完全被覆問題
* 最大独立集合問題

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「最小頂点被覆問題」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.