| 第1章 はじめに 1 |
| 1.1 列挙 2 |
| 1.2 アルゴリズムの計算時間 6 |
| 1.3 線形の最適化問題 9 |
| 1.4 ソーティング 11 |
| 演習問題 13 |
| 参考文献 14 |
| 第2章 グラフ 15 |
| 2.1 基礎的な定義 15 |
| 2.2 木，閉路，カット 20 |
| 2.3 連結性 28 |
| 2.4 オイラーグラフと2部グラフ 35 |
| 2.5 平面性 38 |
| 2.6 平面的双対性 46 |
| 演習問題 48 |
| 参考文献 52 |
| 第3章 線形計画法 54 |
| 3.1 多面体 55 |
| 3.2 単体法 61 |
| 3.3 双対性 66 |
| 3.4 凸包と有界多面体 70 |
| 演習問題 72 |
| 参考文献 74 |
| 第4章 線形計画とアルゴリズム 76 |
| 4.1 頂点と面のサイズ 76 |
| 4.2 連分数 80 |
| 4.3 ガウスの消去法 83 |
| 4.4 楕円体法 88 |
| 4.5 Khachiyanの定理 94 |
| 4.6 分離問題と最適化 96 |
| 演習問題 103 |
| 参考文献 105 |
| 第5章 整数計画法 106 |
| 5.1 多面体の整数包 107 |
| 5.2 ユニモジュラー変換 112 |
| 5.3 完全双対整数性 114 |
| 5.4 完全ユニモジュラー行列 119 |
| 5.5 切除平面法 125 |
| 5.6 ラグランジュ緩和 130 |
| 演習問題 132 |
| 参考文献 135 |
| 第6章 全点木と有向木 138 |
| 6.1 最小全点木問題 139 |
| 6.2 最小重み有向木 145 |
| 6.3 多面体的表現 149 |
| 6.4 全点木と有向木のパッキング 152 |
| 演習問題 156 |
| 参考文献 160 |
| 第7章 最短パス 163 |
| 7.1 1点からの最短パス 164 |
| 7.2 全点間の最短パス 169 |
| 7.3 最小平均長閉路 172 |
| 演習問題 174 |
| 参考文献 176 |
| 第8章 ネットワークフロー 179 |
| 8.1 最大フロー最小カット定理 180 |
| 8.2 Mengerの定理 184 |
| 8.3 Edmonds-Karpアルゴリズム 186 |
| 8.4 ブロックフローと藤重（Fujishige)のアルゴリズム 188 |
| 8.5 Goldberg-Tarjanアルゴリズム 191 |
| 8.6 Gomory-Hu木 196 |
| 8.7 無向グラフの最小カット 202 |
| 演習問題 205 |
| 参考文献 210 |
| 第9章 最小費用フロー 214 |
| 9.1 問題の定式化 214 |
| 9.2 最適性基準 216 |
| 9.3 最小平均長閉路解消アルゴリズム 219 |
| 9.4 最短パス反復アルゴリズム 222 |
| 9.5 Orlinのアルゴリズム 226 |
| 9.6 時変フロー 231 |
| 演習問題 333 |
| 参考文献 237 |
| 第10章 最大マッチング 239 |
| 10.1 2部グラフのマッチング 240 |
| 10.2 Tutte行列 242 |
| 10.3 Tutteの定理 244 |
| 10.4 因子臨界的グラフの耳分解 247 |
| 10.5 Edmondsのマッチングアルゴリズム 253 |
| 演習問題 263 |
| 参考文献 267 |
| 第11章 重み付きマッチング 270 |
| 11.1 割当問題 271 |
| 11.2 重み付きマッチングアルゴリズムの概略 272 |
| 11.3 重み付きマッチングアルゴリズムの実装 275 |
| 11.4 事後最適性 289 |
| 11.5 マッチング多面体 291 |
| 演習問題 294 |
| 参考文献 296 |
| 第12章 ｂ-マッチングとT-ジョイン 298 |
| 12.1 ｂ-マッチング 298 |
| 12.2 最小重みT-ジョイン 303 |
| 12.3 T-ジョインとT-カット 307 |
| 12.4 Padberg-Raoの定理 310 |
| 演習問題 314 |
| 参考文献 317 |
| 第13章 マトロイド 319 |
| 13.1 独立性システムとマドロイド 319 |
| 13.2 他のマトロイド公理系 324 |
| 13.3 双対性 329 |
| 13.4 グリーディ法 333 |
| 13.5 マトロイドの共通独立集合 338 |
| 13.6 マトロイド分割 343 |
| 13.7 重み付きマトロイド交差 345 |
| 演習問題 349 |
| 参考文献 351 |
| 第14章 マトロイドの一般化 354 |
| 14.1 グリードイド 354 |
| 14.2 ポリマトロイド 358 |
| 14.3 劣モジュラー関数の最小化 363 |
| 14.4 Schrijverのアルゴリズム 366 |
| 14.5 対称劣モジュラー関数 371 |
| 演習問題 373 |
| 参考文献 376 |
| 第15章 NP-完全性 378 |
| 15.1 チューリング機械 379 |
| 15.2 Churchの提唱 381 |
| 15.3 PとNP 386 |
| 15.4 Cookの定理 391 |
| 15.5 いくつかの基本的なNP-完全問題 395 |
| 15.6 クラスｃoNP 403 |
| 15.7 NP-困難問題 404 |
| 演習問題 409 |
| 参考文献 412 |
| 第16章 近似アルゴリズム 414 |
| 16.1 集合カバー 415 |
| 16.2 彩色 420 |
| 16.3 近似スキーム 428 |
| 16.4 最大充足化問題 430 |
| 16.5 PCP定理 436 |
| 16.6 L-帰着 440 |
| 演習問題 447 |
| 参考文献 450 |
| 第17章 ナップサック問題 455 |
| 17.1 小数ナップサック問題と重み付き中央値問題 455 |
| 17.2 擬似多項式時間アルゴリズム 458 |
| 17.3 完全多項式近似スキーム 460 |
| 演習問題 463 |
| 参考文献 464 |
| 第18章 ビンパッキング問題 466 |
| 18.1 グリーディ法 467 |
| 18.2 漸近的近似スキーム 472 |
| 18.3 Karmarkar-Karpアルゴリズム 476 |
| 演習問題 480 |
| 参考文献 481 |
| 第19章 多品種フローと辺素パス 484 |
| 19.1 多品種フロー 485 |
| 19.2 多品種フローのアルゴリズム 488 |
| 19.3 有向辺素パス問題 493 |
| 19.4 無向辺素パス問題 497 |
| 演習問題 503 |
| 参考文献 505 |
| 第20章 ネットワーク設計問題 509 |
| 20.1 シュタイナー木 510 |
| 20.2 Robins-Zelikovskyアルゴリズム 515 |
| 20.3 サバイバルネットワーク設計 521 |
| 20.4 主双対近似アルゴリズム 524 |
| 20.5 Jainのアルゴリズム 533 |
| 演習問題 539 |
| 参考文献 542 |
| 第21章 巡回セールスマン問題 546 |
| 21.1 TSPの近似アルゴリズム 546 |
| 21.2 ユークリッドTSP 552 |
| 21.3 場所探索 561 |
| 21.4 巡回セールスマン多面体 568 |
| 21.5 下界 575 |
| 21.6 分枝限定法 577 |
| 演習問題 580 |
| 参考文献 582 |
| 第22章 施設配置問題 586 |
| 22.1 容量制約なし施設配置問題 586 |
| 22.2 線形計画問題の解のラウンディング 588 |
| 22.3 主双対アルゴリズム 590 |
| 22.4 スケール変換とグリーディ増加操作 597 |
| 22.5 開設施設数の制約 601 |
| 22.6 局所探索 605 |
| 22.7 容量制限付き施設配置問題 611 |
| 22.8 普遍的施設配置問題 614 |
| 演習問題 623 |
| 参考文献 625 |
| 訳者あとがき 628 |
| 引用文献著者索引 631 |
| 問題・アルゴリズム索引 639 |
| 事項索引 646 |
図書
