6 citations · 6 across the 4 of their papers we have counts for
3 papers · 2 filters
Fully Dynamic Random-Walk Quantities on Undirected Expanders and -Uniform Directed Graphs
Richard Peng, Sushant Sachdeva, Junzhao Yang +1
We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has sp…
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…
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…