Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
classification
💻 cs.DM
cs.DS
keywords
directedflowgraphsmaximumnodesplanaralgorithmalgorithms
read the original abstract
We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.
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.