2021/01/27 by Enoch, Julian, Fox, Kyle, Mesica, Dor +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2101.11300
We give an O(k3 n log n min(k,log2 n) log2(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(k2,klog2 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(k3 n log3 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].