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 ${\hat{I}}_e^3>0$ governing whe…