Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

Julian Enoch, Kyle Fox, Dor Mesica +1

We give an $O(k^{3}n\log n\min (k,{\log }^{2}n){\log }^2(nC))$-time algorithm for computing maximum integer flows in planar graphs with integer arc {\em and vertex} capacities bounded by…