Shaked Matar

activity

20192021

collaborators

4 papers

cs.DS2021

Ultra-Sparse Near-Additive Emulators

Michael Elkin, Shaked Matar

Near-additive (aka $(1 + ε, β)$ -) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related…

cs.DC2020

Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work

Elkin Michael, Matar Shaked

We study a $(1 + ε)$ -approximate single-source shortest paths (henceforth, $(1 + ε)$ -SSSP) in $n$ -vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A rand…

cs.DC2019

Fast Deterministic Constructions of Linear-Size Spanners and Skeletons

Michael Elkin, Shaked Matar

In the distributed setting, the only existing constructions of \textit{sparse skeletons}, (i.e., subgraphs with $O (n)$ edges) either use randomization or large messages, or require…

cs.DC2019

Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

Michael Elkin, Shaked Matar

Given parameters $α \geq 1, β \geq 0$ , a subgraph $G^{'} = (V, H)$ of an $n$ -vertex unweighted undirected graph $G = (V, E)$ is called an $(α, β)$ -spanner if for every pair $u, v \in V$ of vertic…