エドモンズ・カープのアルゴリズムとは - わかりやすく解説 Weblio辞書

エドモンズ・カープのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:32 UTC 版)

エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 $O(VE^{2})$

一般	バリア関数ペナルティ法（英語版）
微分可能	オーグメンテッド-ラグランジュ法（英語版）逐次二次計画法連続線形計画（英語版）

内点	カチヤン楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	ダンツィクのシンプレックス法改訂シンプレックス法（英語版）十字法（英語版）レムケの主ピボット操作法（英語版）

系列範例
(Paradigms)

最小全域木	ベルマン–フォード法ボルゥースカ法（英語版）ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）

^ E. A. Dinic (1970年). “Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady (Doklady) Vol 11: 1277–1280.
^ Jack Edmonds and Richard M. Karp (1972年). “Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM 19 (2): 248–264.
^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001年). “26.2”. Introduction to Algorithms (second edition ed.). MIT Press and McGraw-Hill. pp. 660-663. ISBN 0-262-53196-8.