最大フロー問題
有向グラフ G ( V , E ) {\displaystyle G(V,E)} において、各枝 u , v {\displaystyle u,v} の容量を c ( u , v ) {\displaystyle c(u,v)} としたとき、始点 s {\displaystyle s} から終点 t {\displaystyle t} への最大フロー f {\displaystyle f} を求める。この問題の解法アルゴリズムは多数存在する。
これら以外にも解法アルゴリズムは多数存在し、参考文献(特に Goldberg and Tarjan 1988)を参照されたい。
doi:10.1145/12130.12144.
↑ King, V.; Rao, S.; Tarjan, R. (1994). “A Faster Deterministic Maximum Flow Algorithm”. Journal of Algorithms 17 (3): 447–474. doi:10.1006/jagm.1994.1044. ISSN 01966774.
↑ Goldberg, Andrew V.; Rao, Satish (1998). “Beyond the flow decomposition barrier”. Journal of the ACM 45 (5): 783–797. doi:10.1145/290179.290181. ISSN 00045411.
↑ Orlin, James B. (2013). Max flows in O(nm) time, or better. pp. 765. doi:10.1145/2488608.2488705.