| 記法一覧 ix |
| 問題一覧 xii |
| アルゴリズム一覧 xiv |
| 第1章 はじめに 1 |
| 1.1 列挙 2 |
| 1.2 アルゴリズムの計算時間 6 |
| 1.3 線形の最適化問題 9 |
| 1.4 ソーティング 11 |
| 演習問題 13 |
| 参考文献 14 |
| 第2章 グラフ 15 |
| 2.1 基礎的な定義 15 |
| 2.2 木，閉路，カット 21 |
| 2.3 連結性 30 |
| 2.4 オイラーグラフと2部グラフ 37 |
| 2.5 平面性 41 |
| 2.6 平面的双対性 49 |
| 演習問題 52 |
| 参考文献 55 |
| 第3章 線形計画法 58 |
| 3.1 多面体 61 |
| 3.2 単体法 68 |
| 3.3 単体法の実装 72 |
| 3.4 双対性 76 |
| 3.5 凸包と有界多面体 80 |
| 演習問題 83 |
| 参考文献 85 |
| 第4章 線形計画アルゴリズム 87 |
| 4.1 頂点と面のサイズ 87 |
| 4.2 連分数 91 |
| 4.3 ガウスの消去法 95 |
| 4.4 楕円体法 100 |
| 4.5 Khachiyanの定理 106 |
| 4.6 分離問題と最適化 109 |
| 演習問題 116 |
| 参考文献 118 |
| 第5章 整数計画法 120 |
| 5.1 多面体の整数包 123 |
| 5.2 ユニモジュラー変換 128 |
| 5.3 完全双対整数性 131 |
| 5.4 完全ユニモジュラー行列 135 |
| 5.5 切除平面法 141 |
| 5.6 ラグランジュ緩和 147 |
| 演習問題 149 |
| 参考文献 152 |
| 第6章 全点木と有向木 155 |
| 6.1 最小全点木問題 156 |
| 6.2 最小重み有向木 163 |
| 6.3 多面体的表現 167 |
| 6.4 全点木と有向木のパッキング 171 |
| 演習問題 175 |
| 参考文献 178 |
| 第7章 最短パス 182 |
| 7.1 1点からの最短パス 183 |
| 7.2 全点間の最短パス 188 |
| 7.3 最小平均長閉路 191 |
| 演習問題 194 |
| 参考文献 195 |
| 第8章 ネットワークフロー 198 |
| 8.1 最大フロー最小カット定理 199 |
| 8.2 Mengerの定理 203 |
| 8.3 Edmonds-Karpアルゴリズム 206 |
| 8.4 ブロックフローと藤重（Fujishige）のアルゴリズム 208 |
| 8.5 Goldberg-Tarjanアルゴリズム 210 |
| 8.6 Gomory-Hu木 215 |
| 8.7 無向グラフの最小容量カット 222 |
| 演習問題 224 |
| 参考文献 230 |
| 第9章 最小費用フロー 234 |
| 9.1 問題の定式化 234 |
| 9.2 最適性基準 236 |
| 9.3 最小平均長閉路解消アルゴリズム 239 |
| 9.4 最短パス反復アルゴリズム 242 |
| 9.5 Orlinのアルゴリズム 247 |
| 9.6 ネットワーク単体法 252 |
| 9.7 時変フロ－ 257 |
| 演習問題 259 |
| 参考文献 263 |
| 第10章 最大マッチング 266 |
| 10.1 2部グラフのマッチング 267 |
| 10.2 Tutte行列 269 |
| 10.3 Tutteの定理 272 |
| 10.4 因子臨界的グラフの耳分解 275 |
| 10.5 Edmondsのマッチングアルゴリズム 281 |
| 演習問題 291 |
| 参考文献 295 |
| 第11章 重み付きマッチング 299 |
| 11.1 割当問題 300 |
| 11.2 重み付きマッチングアルゴリズムの概略 301 |
| 11.3 重み付きマッチングアルゴリズムの実装 304 |
| 11.4 事後最適性 318 |
| 11.5 マッチング多面体 319 |
| 演習問題 323 |
| 参考文献 325 |
| 第12章 b-マッチングとT-ジョイン 327 |
| 12.1 b-マッチング 327 |
| 12.2 最小重みT-ジョイン 332 |
| 12.3 T-ジョインとT-カット 337 |
| 12.4 Padberg-Raoの定理 341、 |
| 演習問題 344 |
| 参考文献 347 |
| 第13章 マトロイド 349 |
| 13.1 独立性システムとマトロイド 349 |
| 13.2 他のマトロイド公理系 354 |
| 13.3 双対性 359 |
| 13.4 グリーディ法 363 |
| 13.5 マトロイドの共通独立集合 369 |
| 13.6 マトロイド分割 374 |
| 13.7 重み付きマトロイド交差 376 |
| 演習問題 380 |
| 参考文献 383 |
| 第14章 マトロイドの一般化 385 |
| 14.1 グリードイド 385 |
| 14.2 ポリマトロイド 390 |
| 14.3 劣モジュラー関数の最小化 394 |
| 14.4 Schrijverのアルゴリズム 397 |
| 14.5 対称劣モジュラー関数 403 |
| 演習問題 405 |
| 参考文献 408 |
| 第15章 NP-完全性 411 |
| 15.1 チューリング機械 412 |
| 15.2 Churchの提唱 414 |
| 15.3 PとNP 419 |
| 15.4 Cookの定理 424 |
| 15.5 いくつかの基本的なNP-完全問題 428 |
| 15.6 クラスcoNP 436 |
| 15.7 NP-困難問題 438 |
| 演習問題 442 |
| 参考文献 446 |
| 第16章 近似アルゴリズム 448 |
| 16.1 集合カバー 449 |
| 16.2 最大カット問題 455 |
| 16.3 彩色 462 |
| 16.4 近似スキーム 470 |
| 16.5 最大充足化問題 473 |
| 16.6 PCP定理 479 |
| 16.7 L-帰着 483 |
| 演習問題 490 |
| 参考文献 494 |
| 第17章 ナップサック問題 499 |
| 17.1 小数ナップサック問題と重み付き中央値問題 499 |
| 17.2 擬似多項式時間アルゴリズム 502 |
| 17.3 完全多項式近似スキーム 504 |
| 演習問題 507 |
| 参考文献 508 |
| 第18章 ビンパッキング問題 510 |
| 18.1 グリーディ法 511 |
| 18.2 漸近的近似スキーム 517 |
| 18.3 Karmarkar-Karpアルゴリズム 521 |
| 演習問題 524 |
| 参考文献 526 |
| 第19章 多品種フローと辺素パス 529 |
| 19.1 多品種フロー 530 |
| 19.2 多品種フローのアルゴリズム 533 |
| 19.3 有向辺素パス問題 538 |
| 19.4 無向辺素パス問題 543 |
| 演習問題 549 |
| 参考文献 552 |
| 第20章 ネットワーク設計問題 556 |
| 20.1 シュタイナー木 557 |
| 20.2 Robins-Zelikovskyアルゴリズム 562 |
| 20.3 サバイバルネットワーク設計 569 |
| 20.4 主双対近似アルゴリズム 572 |
| 20.5 Jainのアルゴリズム 581 |
| 演習問題 588 |
| 参考文献 591 |
| 第21章 巡回セールスマン問題 595 |
| 21.1 TSPの近似アルゴリズム 595 |
| 21.2 ユークリッドTSP 601 |
| 21.3 局所探索 610 |
| 21.4 巡回セールスマン多面体 618 |
| 21.5 下界 624 |
| 21.6 分枝限定法 627 |
| 演習問題 629 |
| 参考文献 633 |
| 第22章 施設配置問題 637 |
| 22.1 容量制約なし施設配置問題 637 |
| 22.2 線形計画問題の解のラウンディング 639 |
| 22.3 主双対アルゴリズム 641 |
| 22.4 スケール変換とグリーディ増加操作 648 |
| 22.5 開設施設数の制約 652 |
| 22.6 局所探索 656 |
| 22.7 容量制約付き施設配置問題 663 |
| 22.8 普遍的施設配置問題 666 |
| 演習問題 675 |
| 参考文献 676 |
| 訳者あとがき 679 |
| 引用文献著者索引 682 |
| 問題・アルゴリズム索引 691 |
| 事項索引 698 |
