7 papers · 1 filter
An Approximation Algorithm for Graph Label Selection
Josia John, Simon Meierhans, Maximilian Probst Gutenberg
In the graph label selection problem, one is given an -vertex graph and a budget , and seeks to select vertices whose labels enable accurate prediction of the labels on t…
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg
Whether a graph is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that…
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions to an -edge graph that is…
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph , a near-optimal -expander decomposition is…
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 with polynomially bounded edge lengths, our data struc…
A Simple Dynamic Spanner via APSP
Rasmus Kyng, Simon Meierhans, Gernot Zöcklein
We give a simple algorithm for maintaining a -approximate spanner of a graph with vertices as receives edge updates by reduction to the dynamic All-Pairs…