2 papers
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…