20 citations · 109 across the 34 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…
Faster Deterministic Fully-Dynamic Graph Connectivity
Christian Wulff-Nilsen
We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in amortized time and…
Connectivity Oracles for Planar Graphs
Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen
We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or…
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 $…