2 citations · 4 across the 4 of their papers we have counts for
4 papers
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…
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…
Improved distance queries in planar graphs
Yahav Nussbaum
There are several known data structures that answer distance queries between two arbitrary vertices in a planar graph. The tradeoff is among preprocessing time, storage space and q…
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…