The most efficient algorithm currently known for computing maximum integer flows in planar graphs with vertex capacities and multiple sources and sinks Wang, SODA 2019%DIFDELCMD < ] %%% runs in O(k ^5n \text{ polylog ] O(k ^4n \text{ polylog ]
 %DIFDELCMD < ] %%% A k-apex graph is a graph with a subset of k vertices, called apices, whose removal makes the graph planar. We present an O(k ^2 n \log^3 n)-time algorithm that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinks T, computes a maximum flow from S to T in G. This improves by a factor of k on the fastest algorithm previously known for this problem Borradaile et al., FOCS 2012, SICOMP 2017]. Our improvement is achieved by introducing a new variant of the push-relabel algorithm for computing maximum flows. We use our improved algorithm for maximum flow in k-apex graphs, together with additional insights, to obtain an O(k ^3 n \polylog(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of k^2 over the fastest algorithm previously known for this problem Wang, SODA 2019].
D
The most efficient algorithm currently known for computing maximum integer flows in planar graphs with vertex capacities and multiple sources and sinks
D
Wang, SODA 2019
R
runs in
A k-apex graph is a graph with a subset of k vertices, called apices, whose removal makes the graph planar. We present an
R
^5n \text{ polylog
^2 n \log^3 n)-time algorithm that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinks T, computes a maximum flow from S to T in G. This improves by a factor of k on the fastest algorithm previously known for this problem
A
Borradaile et al., FOCS 2012, SICOMP 2017
A
. Our improvement is achieved by introducing a new variant of the push-relabel algorithm for computing maximum flows. We use our improved algorithm for maximum flow in k-apex graphs, together with additional insights, to obtain an
R
^4n \text{ polylog
^3 n \
A
polylog
A
(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of k^2 over the fastest algorithm previously known for this problem
A
Wang, SODA 2019
A
.