21 citations · 33 across the 12 of their papers we have counts for
4 papers · 2 filters
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…
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…