Near-Optimal Distributed Maximum Flow

Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn +2

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(…