The Art Gallery Guardian

Maximum flow running time depend on longest path


Consider a directed graph with specified vertices ss and tt. The graph has mm edges and nn vertices with length of the longest simple stst-path to be kk. Dinic’s algorithm finds a maximum flow consists of blocking flow computations, where each takes O(mlogn)O(m\log n) time with dynamic trees [1,2]. After each blocking flow, the distance between ss and tt in the residual graph increases by at least 11. Therefore there are at most kk blocking flow computations. Dinic’s algorithm takes O(kmlogn)O(km\log n) time to find a maximum stst-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.