The Art Gallery Guardian

Maximum flow running time depend on longest path


Consider a directed graph with specified vertices s and t. The graph has m edges and n vertices with length of the longest simple st-path to be k. Dinic's algorithm finds a maximum flow consists of blocking flow computations, where each takes O(m\log n) time with dynamic trees [1,2]. After each blocking flow, the distance between s and t in the residual graph increases by at least 1. Therefore there are at most k blocking flow computations. Dinic's algorithm takes O(km\log n) time to find a maximum st-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 2016-07-02.
Tags: flow.