Approximate undirected maximum flows in O(mpolylog(n)) time

DOI10.1137/1.9781611974331.CH130MaRDI QIDQ4575714zbMATH OpenOpenAlexFDO

Authors Richard Peng

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.7631

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We give the first O(m polylog(n)) time algorithms for approximating maximum flows in undirected graphs and constructing polylog(n) -quality cut-approximating hierarchical tree decompositions. Our algorithm invokes existing algorithms for these two problems recursively while gradually incorporating size reductions. These size reductions are in turn obtained via ultra-sparsifiers, which are key tools in solvers for symmetric diagonally dominant (SDD) linear systems.

Recommendations

• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• A new approach to computing maximum flows using electrical flows
• Approximate maximum flow on separable undirected graphs
• Randomized approximation schemes for cuts and flows in capacitated graphs

Cited in

(23)

• Network essence: PageRank completion and centrality-conforming Markov chains
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Compact oblivious routing
• Hypergraph Cuts with General Splitting Functions
• The power of vertex sparsifiers in dynamic graph algorithms
• Hardness results for structured linear systems
• Computing cut-based hierarchical decompositions in almost linear time
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Approximate maximum flow on separable undirected graphs
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Minimum cost flow in the CONGEST model
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Optimal electrical oblivious routing on expanders
• High-accuracy multicommodity flows via iterative refinement
• Electrical flows for polylogarithmic competitive oblivious routing
• Ultrasparse ultrasparsifiers and faster Laplacian system solvers
• Maximum flow and minimum-cost flow in almost-linear time
• O( n)-approximation algorithms for bipartiteness ratio
• Incremental approximate maximum flow via residual graph sparsification
• Incremental approximate maximum flow via residual graph sparsification

This page was built for publication: Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575714)