We give an O(k^3 n \polylog ( nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex {\em  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]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses k invocations of a maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we introduce a new variant of the push-relabel algorithm of Goldberg and Tarjan and use it to find a maximum flow in the k-apex graphs that arise in  Wang's procedure , faster than the algorithm of Borradaile et al   .
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 C, and k sources and sinks. This improves by a factor of \max(k^2,k\log^2 n) over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses O(k) invocations of an O(k^3 n \log^3 n)-time algorithm for maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the k-apex graphs that arise in our modification of Wang's procedure faster than the algorithm of Borradaile et al . In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan~ JACM 1988 .
D
\
D
polylog
R
(
\log n \min(k,\log^2 n) \log^2(
D
and vertex
A
and vertex
R
k^2
\max(k^2,k\log^2 n)
R
k invocations of a
O(k) invocations of an O(k^3 n \log^3 n)-time algorithm for
R
introduce a new variant of the push-relabel algorithm of Goldberg and Tarjan and use it to find a maximum flow
show two alternatives for computing flows
A
our modification of
D
,
A
. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan~
A
JACM 1988