Christian Wulff-Nilsen

activity

20092026

most citedDeterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

20 citations · 109 across the 34 of their papers we have counts for

collaborators

Showing cs.CGShow all

4 papers · 1 filter

cs.CG2020★ 4 cited

Escaping an Infinitude of Lions

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg +1

We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed $1 + ε$ for some value…

cs.CG2017

Greedy spanners are optimal in doubling metrics

Glencora Borradaile, Hung Le, Christian Wulff-Nilsen

We show that the greedy spanner algorithm constructs a $(1 + ε)$ -spanner of weight $ε^{- O (d)} w (MST)$ for a point set in metrics of doubling dimension $d$ , resolving an open…

cs.CG2017★ 2 cited

Best Laid Plans of Lions and Men

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg +1

We study the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assume…

cs.CG2014

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Glencora Borradaile, David Eppstein, Amir Nayyeri +1

For an undirected $n$ -vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$ , what is the weight of a minim…