第１章最短パスアルゴリズムの概略
- １．１すべての辺が非負コストのケース：Ｄｉｊｋｓｔｒａのアルゴリズム
- １．２負コストの辺もあるケース：Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズム
- １．３負コスト閉路の検出
第２章最大フローアルゴリズム
- ２．１最適性条件
- ２．２応用１：相乗り運転手割当問題
- ２．３応用２：プロ野球リーグにおけるチームの優勝可能性の消滅判定
- ２．４応用３：密度最大の部分グラフの発見
- ２．５最良改善増加パスアルゴリズム
- ２．６容量スケーリングアルゴリズム
- ２．７最短増加パスアルゴリズム
- ２．８プッシュ再ラベルアルゴリズム
第３章大域的最小カットアルゴリズム
- ３．１Ｈａｏ−Ｏｒｌｉｎアルゴリズム
- ３．２ＭＡ順序アルゴリズム
- ３．３乱択縮約アルゴリズム
- ３．４Ｇｏｍｏｒｙ−Ｈｕ木
第４章さらなる最大フローアルゴリズム
- ４．１ブロックフロー
- ４．２単位容量グラフにおけるブロックフロー
- ４．３Ｇｏｌｄｂｅｒｇ−Ｒａｏアルゴリズム
第５章最小コスト循環フローアルゴリズム
- ５．１最適性条件
- ５．２Ｗａｌｌａｃｈｅｒのアルゴリズム
- ５．３最小平均長閉路消去アルゴリズム
- ５．４容量スケーリングアルゴリズム
- ５．５逐次近似アルゴリズム
- ５．６ネットワークシンプレックス法
- ５．７応用：最大時変フロー
第６章一般化フローアルゴリズム
- ６．１最適性条件
- ６．２Ｗａｌｌａｃｈｅｒ形式のＧＡＰ−消去アルゴリズム
- ６．３負コストＧＡＰの検出
- ６．４損失グラフとＴｒｕｅｍｐｅｒのアルゴリズムと利得スケーリング
- ６．５誤差スケーリング
第７章多品種フローアルゴリズム
- ７．１最適性条件
- ７．２２品種のケース
- ７．３間奏：乗法的重み付けアルゴリズム
- ７．４Ｇａｒｇ−Ｋöｎｅｍａｎｎアルゴリズム
- ７．５Ａｗｅｒｂｕｃｈ−Ｌｅｉｇｈｔｏｎアルゴリズム
第８章電流アルゴリズム
- ８．１最適性条件
- ８．２無向グラフの最大フロー
- ８．３グラフスパース化
- ８．４単純なラプラシアンソルバー
第９章未解決問題