Yuval Gitlitz

activity

20202024

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2024

Lightweight Near-Additive Spanners

Yuval Gitlitz, Ofer Neiman, Richard Spence

An $(α, β)$ -spanner of a weighted graph $G = (V, E)$ , is a subgraph $H$ such that for every $u, v \in V$ , $d_{G} (u, v) \leq d_{H} (u, v) \leq α \cdot d_{G} (u, v) + β$ . The main parameters of interest for…

cs.DS2023

Light, Reliable Spanners

Arnold Filtser, Yuval Gitlitz, Ofer Neiman

A \emph{ $ν$ -reliable spanner} of a metric space $(X, d)$ , is a (dominating) graph $H$ , such that for any possible failure set $B \subseteq X$ , there is a set $B^{+}$ just slightly larg…

cs.DS2020

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…