D. P. ウィリアムソン 　著

内容

目次

序文 謝辞 日本語版への序文 アルゴリズム一覧 第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章　未解決問題 参考文献 訳者あとがき 著者索引 英文事項索引 和文事項索引