Improved Parallel Algorithms for Spanners and Hopsets
Gary Lee Miller, Richard Peng, Adrian Vladu, Shen Xu · 2015
We use exponential start time clustering to design faster parallel graph algorithms involving distances. Previous algorithms usually rely on graph decomposition routines with strict restrictions on the diameters of the decomposed pieces. We weaken these bounds in favor of stronger local probabilistic guarantees. This allows more direct analyses of the overall process, giving: