62 citations · 316 across the 38 of their papers we have counts for
3 papers · 1 filter
A Tight Bound for Shortest Augmenting Paths on Trees
Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski +1
The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it…
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…
Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen
For an undirected -vertex planar graph with non-negative edge-weights, we consider the following type of query: given two vertices and in , what is the weight of…