最小頂点被覆問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 最小頂点被覆問題の意味・解説 

最小頂点被覆問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/14 05:15 UTC 版)

ナビゲーションに移動 検索に移動

最小頂点被覆問題(さいしょうちょうてんひふくもんだい)は、計算複雑性理論におけるNP困難な問題の一つ。

問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′| が最小になるものを求めよ

この問題の最適解を求めるのは、NP困難なため、決定性の多項式時間アルゴリズムは存在しないと考えられている。近似アルゴリズムに関して言えば、近似度2の貪欲アルゴリズムが存在することが知られているが、任意の ε > 0 について、近似度 2 - ε の近似度を達成するアルゴリズムも存在しないだろうと考えられている。2005年現在の最良の近似度の下限は、 である。

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「最小頂点被覆問題」の関連用語

最小頂点被覆問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



最小頂点被覆問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの最小頂点被覆問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS