Content deleted Content added
Line 9:
The concept of a preflow was originally designed by Alexander V. Karzanov and was published in 1974 in Soviet Mathematical Dokladi 15. This pre-flow algorithm also used a push operation; however, it used distances in the auxiliary network to determine where to push the flow instead of a labeling system.<ref name="goldberg86"/><ref name="goldberg2014"/>
The push-relabel algorithm was designed by [[Andrew V. Goldberg]] and [[Robert Tarjan]]. The algorithm was initially presented in November 1986 in STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, and then officially in October 1988 as an article in the Journal of the ACM. Both papers detail a generic form of the algorithm terminating in {{math|''O''(''V''<sup> 2</sup>''E'')}} along with a {{math|''O''(''V''<sup> 3</sup>)}} sequential implementation, a {{math|''O''(''VE''log(''V''<sup> 2</sup>/''E''))}} implementation using dynamic trees, and parallel/distributed implementation.<ref name="goldberg86"/><ref name="goldberg88"/>. A explained in <ref name="amo93"/> Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and [[Uzi Vishkin]] <ref name="sv82"/>.
==Concepts==
| |||