Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1

Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $\varphi$-expander decomposition is…