Yuval Gitlitz

activity

20192024

collaborators

4 papers

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…

cs.DS2019

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Michael Elkin, Yuval Gitlitz, Ofer Neiman

Let $G = (V, E, w)$ be a weighted undirected graph with $n$ vertices and $m$ edges, and fix a set of $s$ sources $S \subseteq V$ . We study the problem of computing {\em almost shortest…