4 papers
Parallel Spectral Graph Sparsification via Low Diameter Decompositions
Yves Baumann, Gernot Zöcklein
We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This…
An Online Sparsification Algorithm from the Book
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R…
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…