計算問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 03:31 UTC 版)
最小頂点被覆問題は、与えられたグラフの最小頂点被覆を求める最適化問題である。 INSTANCE: グラフ G OUTPUT: G の頂点被覆 C の大きさ k について、最小のもの。 決定問題とする場合は、これを頂点被覆問題と呼び、次のように定式化される。 INSTANCE: グラフ G と正の整数 k QUESTION: G の頂点被覆 C で、その大きさが k 以下のものがあるか? 頂点被覆問題はNP完全問題である。カープの21のNP完全問題の1つになっており、他の問題がNP困難であることを示す手段として計算複雑性理論でよく利用される。
※この「計算問題」の解説は、「頂点被覆」の解説の一部です。
「計算問題」を含む「頂点被覆」の記事については、「頂点被覆」の概要を参照ください。
ウィキペディア小見出し辞書の「計算問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
このページでは「ウィキペディア小見出し辞書」から計算問題を検索した結果を表示しています。
Weblioに収録されているすべての辞書から計算問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算問題
を検索
Weblioに収録されているすべての辞書から計算問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算問題
を検索
- 計算問題のページへのリンク
