NEAR-OPTIMAL DISTRIBUTED MAXIMUM FLOW

Ghaffari, M; Karrenbauer, A; Kuhn, F; Lenzen, C; Patt-Shamir, B

Ghaffari, M (reprint author), Swiss Fed Inst Technol, Comp Sci Dept, CH-8092 Zurich, Switzerland.

SIAM JOURNAL ON COMPUTING, 2018; 47 (6): 2078

Abstract

We present a near-optimal distributed algorithm for (1 + o(1))-approximation of single-commodity maximum flow in undirected weighted networks that run......

Full Text Link