最大フロー問題については、いくつかの非常に洗練されたアルゴリズムがあるようで、少なくとも 1 つが昨年開発されました。Orlin の最大フローは O(mn) 時間またはそれ以上で、O(VE) で実行されるアルゴリズムを提供します。
一方、私が最も一般的に実装しているアルゴリズムは次のとおりです (徹底的な検索を行ったとは言いません。これは、何気なく観察しただけです)。
- エドモンズ・カープ、O(VE^2)
- FIFO 頂点選択を使用したプッシュ リラベル、O(V^2 E)、または O(V^3)
- Dinic のアルゴリズム、O(V^2 E)
より良い漸近実行時間を持つアルゴリズムは、現実世界の問題サイズに対して実用的ではないのでしょうか? また、「動的ツリー」がかなりの数のアルゴリズムに関与していることがわかります。これらは実際に使用されていますか？