20 citations · 109 across the 34 of their papers we have counts for
12 papers · 1 filter
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…
Approximate Distance Oracles with Improved Query Time
Christian Wulff-Nilsen
Given an undirected graph with edges, vertices, and non-negative edge weights, and given an integer , we show that a -approximate distance oracle for $…
Approximate Distance Oracles with Improved Preprocessing Time
Christian Wulff-Nilsen
Given an undirected graph with edges, vertices, and non-negative edge weights, and given an integer , we show that for some universal constant , a -…
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
Christian Wulff-Nilsen
Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator theorem and showed that a -minor free graph with vertices has a separator of size at most $h^{3/…
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, single sink maximum flow in a planar graph
Glencora Borradaile, Christian Wulff-Nilsen
We give an time algorithm for finding the maximum flow in a directed planar graph with multiple sources and a single sink. The techniques generalize to a subquad…