Routing under balance
Alina Ene, Gary Lee Miller, Jakub Pachocki, Aaron Sidford · 2016
We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut S ⊆ V, the total weight of edges going from S to V∖ S is within factor α of the total weight of edges going from V∖ S to S. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with α = 1) and residual graphs of (1+є)-approximate undirected maximum flows (with α=O(1/є)).