3 citations · 15 across the 10 of their papers we have counts for
5 papers · 1 filter
Min-Cost Flow Duality in Planar Networks
Haim Kaplan, Yahav Nussbaum
In this paper we study the min-cost flow problem in planar networks. We start with the min-cost flow problem and apply two transformations, one is based on geometric duality of pla…
Single Source - All Sinks Max Flows in Planar Digraphs
Jakub Łącki, Yahav Nussbaum, Piotr Sankowski +1
Let G = (V,E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t in V\{s}. We show how to solve this probl…
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…
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…