タイトルコード |
1000101127703 |
書誌種別 |
図書 |
書名 |
ネットワークフローアルゴリズム |
書名ヨミ |
ネットワーク フロー アルゴリズム |
言語区分 |
日本語 |
著者名 |
D.P.ウィリアムソン/著
浅野 孝夫/訳
浅野 泰仁/訳
|
著者名ヨミ |
D P ウィリアムソン アサノ タカオ アサノ ヤスヒト |
著者名原綴 |
Williamson David P. |
出版地 |
東京 |
出版者 |
丸善出版
|
出版年月 |
2024.1 |
本体価格 |
¥8500 |
ISBN |
978-4-621-30907-0 |
ISBN |
4-621-30907-0 |
数量 |
15,386p |
大きさ |
21cm |
分類記号 |
417
|
件名 |
ネットワーク手法
アルゴリズム
|
注記 |
原タイトル:Network flow algorithms |
注記 |
文献:p345〜357 |
内容紹介 |
組合せ的最適化アルゴリズム研究の第一人者が、簡潔性に主眼を置き、ネットワークフロー問題に対する組合せ的多項式時間アルゴリズムとその解析を第一義的に取り上げ系統的に解説する。 |
目次タイトル |
第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章 未解決問題 |