5 papers · 1 filter
Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg +3
Given an undirected weighted graph , a -approximate low-stretch spanning tree (LSST) is a tree that approximates the distance metric of up to a -factor…
VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization
Yves Baumann, Rasmus Kyng, Gernot Zöcklein
We propose Volume Appproximate Cholesky (VAC), an alternative sampling rule for practical approximate Cholesky algorithms. Our rule samples a uniformly random spanning tree of the…
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…
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…