最小頂点被覆問題のソースを表示
←
最小頂点被覆問題
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、次のグループに属する利用者のみが実行できます:
登録利用者
。
このページのソースの閲覧やコピーができます。
'''最小頂点被覆問題'''(さいしょうちょうてんひふくもんだい)は、[[計算複雑性理論]]における[[NP困難]]な問題の一つ。 問題: [[グラフ理論|グラフ]] ''G''(''V'', ''E'') の各枝 ''e'' について端点のいずれか少なくとも一方が、''V''′ に含まれるような ''V'' の部分集合 ''V''′ のうち、|''V''′| が最小になるものを求めよ この問題の最適解を求めるのは、NP困難なため、決定性の[[多項式時間アルゴリズム]]は存在しないと考えられている。[[近似アルゴリズム]]に関して言えば、近似度2の[[貪欲アルゴリズム]]が存在することが知られているが、任意の ε > 0 について、近似度 2 - ε の近似度を達成するアルゴリズムも存在しないだろうと考えられている。[[2005年]]現在の最良の近似度の下限は、<math>10\sqrt{5}-21 (>1.36)</math> である。 == 関連項目 == * [[頂点被覆]] * [[最適化問題]] * [[完全被覆問題]] * [[最大独立集合問題]] == 外部リンク == * [http://www.nada.kth.se/~viggo/wwwcompendium/node10.html MINIMUM VERTEX COVER] {{DEFAULTSORT:さいしようちようてんひふくもんたい}} [[Category:グラフ理論における計算問題]] [[Category:NP完全問題]] [[Category:数学に関する記事]] [[en:Covering (graph theory)]] [[he:כיסוי (תורת הגרפים)]]
最小頂点被覆問題
に戻る。
ナビゲーション メニュー
個人用ツール
ログイン
名前空間
ページ
議論
日本語
表示
閲覧
ソースを閲覧
履歴表示
その他
検索
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
ツール
リンク元
関連ページの更新状況
ページ情報