Dinic's algorithm
Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
Yefim Dinitz invented this algorithm in response to a pre-class exercise in Adelson-Velsky's algorithms class. At the time he was not aware of the basic facts regarding the Ford–Fulkerson algorithm.
Dinitz mentions inventing his algorithm in January 1969, which was published in 1970 in the journal Doklady Akademii nauk SSSR. In 1974, Shimon Even and (his then Ph.D. student) Alon Itai at the Technion in Haifa were very curious and intrigued by Dinitz's algorithm as well as Alexander Karzanov's idea of blocking flow. However it was hard for them to decipher these two papers, each being limited to four pages to meet the restrictions of journal Doklady Akademii nauk SSSR. Even did not give up, and after three days of effort managed to understand both papers except for the layered network maintenance issue. Over the next couple of years, Even gave lectures on "Dinic's algorithm", mispronouncing the name of the author while popularizing it. Even and Itai also contributed to this algorithm by combining BFS and DFS, which is the current version of the algorithm.
...
Wikipedia