発表年 | 名称 | 計算量 | 説明 |
| 線形計画法 | | 正規フローの定義から制約条件が与えられる。 を最大化。 |
1956年 | フォード・ファルカーソンのアルゴリズム | | 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。 |
1970年 | エドモンズ・カープのアルゴリズム | | フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。 |
1970年 | Dinic法 | | ステップ毎に残余グラフについて幅優先探索で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは で求められ、ステップの反復は最大 回である。 |
1978年 | MPM法[2] | | Malhotra, Pramodh-Kumar, Maheshwari が発表。 |
1981年 | 動的木を使ったDinic法[3] | | 層別グラフのブロッキングフロー計算を動的木を使うことで で行う。 |
1986年 | 汎用プッシュ再ラベル法[4] | | プリフロー(頂点群で超過する可能性のあるフロー関数)を使うアルゴリズム。正の超過のある頂点(グラフ内のアクティブな頂点)がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。 |
1986年 | FIFO式頂点選択規則付きプッシュ再ラベル法[4] | | 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。 |
1986年 | 動的木を使ったプッシュ再ラベル法[4] | | height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。 |
1994年 | KRT (King, Rao, Tarjan) 法[5] | | |
1998年 | バイナリブロッキングフロー法[6] | | 計算量のUはネットワークの最大容量。 |
2013年 | Jim Orlin法 + KRT (King, Rao, Tarjan) 法[7] | | Jim Orlin法自体はだが、KRT法を組み合わせることでになる。 |