1 citations · 1 across the 2 of their papers we have counts for
5 papers · 1 filter
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…
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an -edge graph undergoing edge inse…
Derandomizing Directed Random Walks in Almost-Linear Time
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions…