内容紹介
組合せ最適化，情報科学，離散数学などの複数の研究分野にまたがるネットワークフロー理論の成果と実際問題への応用は膨大であり，完璧な網羅と簡潔性を両立することは困難である．本書は簡潔性に主眼を置き，ネットワークフロー問題に対する組合せ的多項式時間アルゴリズムとその解析を第一義的に取り上げ系統的な解説を与えている．
従来の古典的なネットワークフローの成果に加えて，大域的最小カット問題，最大一般化フロー問題，多品種フロー問題に対する興味深い組合せ的多項式時間アルゴリズムや電気回路の電流解析による高速化アルゴリズムが，近年堰を切ったように発見されてきている．
本書は，組合せ的最適化アルゴリズム研究の第一人者である著者の視点から，これらのアルゴリズムも含めて，ネットワークフロー研究を偏見なく評価し，真に美しく有用なアルゴリズムのアイデアにあふれるこの分野を学ぶための適切な選択とアレンジを提供している．
目次
序文
謝辞
日本語版への序文
アルゴリズム一覧
第1章 最短パスアルゴリズムの概略
1.1 すべての辺が非負コストのケース：Dijkstraのアルゴリズム
1.2 負コストの辺もあるケース：Bellman–Fordアルゴリズム
1.3 負コスト閉路の検出
演習問題
章末ノート
第2章 最大フローアルゴリズム
2.1 最適性条件
2.2 応用1：相乗り運転手割当問題
2.3 応用2：プロ野球リーグにおけるチームの優勝可能性の消滅判定
2.4 応用3：密度最大の部分グラフの発見
2.5 最良改善増加パスアルゴリズム
2.6 容量スケーリングアルゴリズム
2.7 最短増加パスアルゴリズム
2.8 プッシュ再ラベルアルゴリズム
演習問題
章末ノート
第3章 大域的最小カットアルゴリズム
3.1 Hao–Orlinアルゴリズム
3.2 MA順序アルゴリズム
3.3 乱択縮約アルゴリズム
3.4 Gomory–Hu木
演習問題
章末ノート
第4章 さらなる最大フローアルゴリズム
4.1 ブロックフロー
4.2 単位容量グラフにおけるブロックフロー
4.3 Goldberg–Raoアルゴリズム
演習問題
章末ノート
第5章 最小コスト循環フローアルゴリズム
5.1 最適性条件
5.2 Wallacherのアルゴリズム
5.3 最小平均長閉路消去アルゴリズム
5.4 容量スケーリングアルゴリズム
5.5 逐次近似アルゴリズム
5.6 ネットワークシンプレックス法
5.7 応用：最大時変フロー
演習問題
章末ノート
第6章 一般化フローアルゴリズム
6.1 最適性条件
6.2 Wallacher形式のGAP-消去アルゴリズム
6.3 負コストGAPの検出
6.4 損失グラフとTruemperのアルゴリズムと利得スケーリング
6.5 誤差スケーリング
演習問題
章末ノート
第7章 多品種フローアルゴリズム
7.1 最適性条件
7.2 2品種のケース
7.3 間奏：乗法的重み付けアルゴリズム
7.4 Garg–Könemannアルゴリズム
7.5 Awerbuch–Leightonアルゴリズム
演習問題
章末ノート
第8章 電流アルゴリズム
8.1 最適性条件
8.2 無向グラフの最大フロー
8.3 グラフスパース化
8.4 単純なラプラシアンソルバー
演習問題
章末ノート
第9章 未解決問題
参考文献
訳者あとがき
著者索引
英文事項索引
和文事項索引
