20 citations · 109 across the 34 of their papers we have counts for
42 papers
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph undergoes a sequence of edge weight updates and the goal is to maintain a data struct…
VC Set Systems in Minor-free (Di)Graphs and Applications
Hung Le, Christian Wulff-Nilsen
A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter, who constructed a new VC set system for planar graphs, has given surprising…
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai +3
Given a simple -vertex, -edge graph undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G…
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
We present a randomized algorithm that computes single-source shortest paths (SSSP) in time when edge weights are integral and can be negative. This essential…
Optimal Approximate Distance Oracle for Planar Graphs
Hung Le, Christian Wulff-Nilsen
A -approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a $(1+ε)…
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg +1
Given an -vertex planar embedded digraph with non-negative edge weights and a face of , Klein presented a data structure with space and preprocessing tim…