The Art Gallery Guardian

Maximum flow running time depend on longest path


Consider a directed graph with specified vertices and . The graph has edges and vertices with length of the longest simple -path to be . Dinic’s algorithm finds a maximum flow consists of blocking flow computations, where each takes time with dynamic trees [1,2]. After each blocking flow, the distance between and in the residual graph increases by at least . Therefore there are at most blocking flow computations. Dinic’s algorithm takes time to find a maximum -flow.

References

[1]
D.D. Sleator, R.E. Tarjan, A Data Structure for Dynamic Trees, J. Comput. Syst. Sci. 26 (1983) 362–391 10.1016/0022-0000(83)90006-5.
[2]
Y. Dinitz, Theoretical computer science, in: O. Goldreich, A.L. Rosenberg, A.L. Selman (Eds.), Springer-Verlag, Berlin, Heidelberg, 2006: pp. 218–240.
Posted by Chao Xu on .
Tags: flow.