Gernot Zöcklein

collaborators

2 papers

cs.DS2024

Bootstrapping Dynamic APSP via Sparsification

Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph $G = (V, E, l)$ with polynomially bounded edge lengths, our data struc…

cs.DS2024

A Simple Dynamic Spanner via APSP

Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

We give a simple algorithm for maintaining a $n^{o (1)}$ -approximate spanner $H$ of a graph $G$ with $n$ vertices as $G$ receives edge updates by reduction to the dynamic All-Pairs…