Routing under balance

DOI10.1145/2897518.2897654zbMath1373.68302arXiv1603.09009OpenAlexW2319135850MaRDI QIDQ5361864

Alina Ene, Jakub W. Pachocki, Aaron Sidford, Gary Lee Miller

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

directed graphsmaximum flowoblivious routinggradient descentgraph clusteringbalanced directed graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Related Items

Local Flow Partitioning for Faster Edge Connectivity ⋮ A fast algorithm for source-wise round-trip spanners