導入
これは、アルゴリズムの複雑さ理論で最もよく知られている NP 完全問題のリストであり、決定問題として表されます。私たちは 3000 を超える NP 完全問題を知っているため、このリストはすべてを網羅しているわけではありません。リストされている問題のほとんどは、Garey と Johnson の独創的な著書「Computers and Intractability: A Guide to the Theory of NP-Completeness」から来ています。これらは、同じ順序と構成に従ってここに示されています。
アルゴリズム幾何学
- 平面内の一連の点の重みを最小にする三角形分割
- ツリーがユークリッド最小全域木として表現できるかどうかをテストする
- 単位円板のグラフの認識（単位円の平面上の交点グラフです）
- 平面内の多角形の障害物を通過するモーションを計画する問題の多くは NP 困難です。
ネットワーク設計
木を覆う
次数制約スパニングツリー・最大リーフスパニングツリー・最短合計パス長スパニングツリー・有界直径スパニングツリー・容量容量スパニングツリー・幾何容量容量スパニングツリー・最適通信スパニングツリー・同型スパニングツリー・K番目最良スパニングツリー・有界コンポーネントスパニングフォレスト・多肢選択分岐・シュタイナーツリー・幾何学的シュタイナーツリー・ケーブルトレンチ問題
停止と接続
グラフ分割·非巡回分割·最大重みカット·有界セットへの最小カット·双方向接続性の拡張·強力な接続性の拡張·ネットワークの信頼性·ネットワークの存続可能性·マルチウェイ カット·最小 K カット
ルーティング
ボトルネック巡回セールスマン·混合グラフの中国郵便配達員· ユークリッド巡回セールスマン· K 個の最も重要なアーク· K 番目の最短パス·メトリック巡回セールスマン·最長回路·最長パス·賞品収集巡回セールスマン·田舎の郵便配達員· 一般ネットワークにおける最短パス·最短重み-制約された経路·スタッカークレーン· 時間制約のある巡回セールスマンの実現可能性· 巡回セールスマン問題 · 車両ルート問題
流れ
最小エッジコストフロー·乗算器を備えた積分フロー·パス制約のあるネットワークフロー·相同アークを備えた積分フロー·バンドルを備えた積分フロー · 下限のある無向フロー·有向 2 商品積分フロー·無向 2 商品積分フロー·互いに素な接続パス·最大長が制限された素のパス·最大の固定長の素のパス·分割不可能なマルチコモディティ フロー
その他
二次割り当て問題· PERT ネットワークにおけるダミー アクティビティの最小化·制約付き三角形分割· グリッド上のセグメントの交差グラフ·グリッド上のエッジ埋め込み·幾何学的接続支配集合·最小ブロードキャスト時間·最小-最大マルチセンター·最小-合計マルチセンター·容量のない施設の場所·メートル法 k 中心
グラフ理論
カバーと間仕切り
頂点カバー · ドミナント集合 · ドマティック数· Kカラーグラフカラーリング· 無彩色数 · 単色三角形·フィードバック頂点集合·フィードバック弧集合· 部分フィードバック辺集合·最小最大ペアリング·三角形分割·同型部分グラフの分割·ハミルトン部分グラフの分割·フォレストでの分割·クリークでの分割· 完全なペアでの分割· 2 段階の最大重み確率的ペアリング·クリークによるカバレッジ· 完全な 2 部サブグラフによるカバレッジ
サブグラフとスーパーグラフ
。最大のクリック感。最大安定 · 独立集合 ·プロパティ Pi を持つ誘導サブグラフ· プロパティ Pi を持つ誘導接続サブグラフ·誘導パス· バランスのとれた完全な 2 部サブグラフ· 2 部サブグラフ·次数制限された接続サブグラフ· 平面サブグラフ ·エッジサブグラフ·推移サブグラフ·非接続サブグラフ·最小k連結部分グラフ・3次部分グラフ・最小等価有向グラフ・ハミルトニアン完成・区間グラフ完成・パスグラフ完成
頂点の並べ替え
ハミルトニアン サイクル ・有向ハミルトニアン サイクル ・ ハミルトニアンパス・帯域幅・有向帯域幅・最適線形配置・有向最適線形配置・ミニマムカット線形配置・ルートツリー配置・有向消去順序・消去次数列
変形
部分グラフ同型性·最大共通部分グラフ·最大部分グラフ一致·グラフ収縮性·ダイグラフ D 射
その他
禁止されたペアを持つパス·複数選択マッチング·グラフ グランディ番号付け·カーネル· Kクロージャ ·交差グラフの基礎·パス識別子·メトリック次元·ネセトリル-レードル次元·しきい値番号·配向直径·加重直径