Qiitaに記事を投稿しました。
概要
preflow-push algorithm はネットワーク G=(V, E)上の最大フローを求めるアルゴリズムです.
(中略)
この記事では, 計算量を削減する改良として, FIFO Preflow-Push AlgorithmとHighest-Label Preflow-Push Algorithmを, 最悪計算量は変わらないheuristicsな改善手法として, Global labeling, Gap-relabeling, Freeze operationを紹介したいと思います.
参考文献
[1] Goldberg, Andrew V., and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM) 35.4 (1988): 921-940.
[2] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows Theory, Algorithms, and Applications. Prentice-Hall, 1993.
[3]@a-lilas, 最大流問題をプリフロー・プッシュ (Push-Relabel) 法 で解く
[4] 岩野和生, 最大流アルゴリズムの最近の発展とその背景-II, 情報処理 Vol. 31 No.1 (1990)
[5] J.Kleinberg, E. Tardos(著), 浅野孝夫, 浅野泰仁, 小野孝男, 平田富夫(翻訳) (2009) アルゴリズムデザイン*, 共立出版.
