サブロウ丸

主にプログラミングと数学

Preflow Push-Relabel アルゴリズム 改良

Qiitaに記事を投稿しました。

qiita.com

f:id:inarizuuuushi:20181108163007g:plain

概要

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)
アルゴリズムデザイン*, 共立出版.

今回作成したコード

Git Hub上で公開しています。

https://github.com/nariaki3551/max-flow