Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak · Society for Industrial and Applied Mathematics eBooks · 2025
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 ø-expander decomposition is a partition V1, V2,. ., Vk of the vertex set V where each subgraph G [Vi] is a ø-expander, and only an Õ (ø )-fraction of the edges cross between partition sets.