Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Massively Parallel Algorithms for Approximate Shortest Paths
Michal Dory, Shaked Matar
We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take rounds…
cs.DS2021
Ultra-Sparse Near-Additive Emulators
Michael Elkin, Shaked Matar
Near-additive (aka -) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related…