Faster Approximation of Max Flow for Directed Graphs
classification
💻 cs.DM
cs.DS
keywords
directedflowgraphsapproximationfasteralgorithmapproximatelychristiano
read the original abstract
I extend the methods in "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, with Paul Christiano, Jonathan Kelner, Daniel Spielman, and Shang-Hua Teng" to directed graphs with a variation of the framework in the paper, which lead to an algorithm that approximately solves the directed max flow problem in nearly-linear time.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.