2 citations · 4 across the 4 of their papers we have counts for
Showing cs.DMShow all
3 papers · 1 filter
cs.DM2011★ 1 cited
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Glencora Borradaile, Philip N. Klein, Shay Mozes +2
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 sou…
cs.DM2010★ 1 cited
Multiple-source multiple-sink maximum flow in planar graphs
Yahav Nussbaum
In this paper we show an O(n^(3/2) log^2 n) time algorithm for finding a maximum flow in a planar graph with multiple sources and multiple sinks. This is the fastest algorithm whos…
cs.DM2009
Maximum Flow in Directed Planar Graphs with Vertex Capacities
Haim Kaplan, Yahav Nussbaum
In this paper we present an O(n log n) algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the a…