86 citations · 136 across the 29 of their papers we have counts for
44 papers
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari +4
This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algori…
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
Václav Rozhoň, Michael Elkin, Christoph Grunau +1
This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approxim…
-Approximate Shortest Paths in Dynamic Streams
Michael Elkin, Chhaya Trehan
Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied during the last decade. Currently existing soluti…
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…
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work
Elkin Michael, Matar Shaked
We study a -approximate single-source shortest paths (henceforth, -SSSP) in -vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A rand…
Improved Weighted Additive Spanners
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanner…