Shaked Matar

activity

20192024

collaborators

Showing 2019Show all

2 papers · 1 filter

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…