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 http://dx.doi.org/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.