3 papers
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…
cs.DS2025
Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
Yibin Zhao
Recent years have seen extensive research on directed graph sparsification. In this work, we initiate the study of fast fully dynamic spectral and cut sparsification algorithms for…
cs.DS2024
Eulerian Graph Sparsification by Effective Resistance Decomposition
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2
We provide an algorithm that, given an -vertex -edge Eulerian graph with polynomially bounded weights, computes an -edge $\vare…