3 citations · 7 across the 3 of their papers we have counts for
4 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…
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…
Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights
Christian Wulff-Nilsen
Let be a fixed graph and let be an -minor free -vertex graph with integer edge weights and no negative weight cycles reachable from a given vertex . We present an…
Min st-Cut of a Planar Graph in O(n loglog n) Time
Christian Wulff-Nilsen
Given a planar undirected n-vertex graph G with non-negative edge weights, we show how to compute, for given vertices s and t in G, a min st-cut in G in O(n loglog n) time and O(n)…