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…