Generalized Flow in Nearly-linear Time on Moderately Dense Graphs

Shunhua Jiang, Michael Kapralov, Lawrence Li +1

In this paper we consider generalized flow problems where there is an $m$-edge $n$-node directed graph $G=(V,E)$ and each edge $e\in E$ has a loss factor ${\gamma }_e>0$ governing whet…