3 papers
cs.DS2026
Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data struc…
cs.DS2026
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…
cs.DS2026
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…