Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
From MaRDI portal
Publication:4575714
DOI10.1137/1.9781611974331.ch130zbMath1410.68306arXiv1411.7631OpenAlexW2949824190MaRDI QIDQ4575714
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)
Related Items (12)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Hypergraph Cuts with General Splitting Functions ⋮ 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 ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Hardness Results for Structured Linear Systems ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
