Zobrazeno 1 - 10
of 142
pro vyhledávání: '"Neiman, Ofer"'
An $(\alpha,\beta)$-spanner of a weighted graph $G=(V,E)$, is a subgraph $H$ such that for every $u,v\in V$, $d_G(u,v) \le d_H(u,v)\le\alpha\cdot d_G(u,v)+\beta$. The main parameters of interest for spanners are their size (number of edges) and their
Externí odkaz:
http://arxiv.org/abs/2410.23826
Autor:
Neiman, Ofer, Shabat, Idan
Given an undirected weighted graph, an (approximate) distance oracle is a data structure that can (approximately) answer distance queries. A {\em Path-Reporting Distance Oracle}, or {\em PRDO}, is a distance oracle that must also return a path betwee
Externí odkaz:
http://arxiv.org/abs/2405.14254
Autor:
Neiman, Ofer, Shabat, Idan
Given an undirected possibly weighted $n$-vertex graph $G=(V,E)$ and a set $\mathcal{P}\subseteq V^2$ of pairs, a subgraph $S=(V,E')$ is called a ${\cal P}$-pairwise $\alpha$-spanner of $G$, if for every pair $(u,v)\in\mathcal{P}$ we have $d_S(u,v)\l
Externí odkaz:
http://arxiv.org/abs/2311.13673
A \emph{$\nu$-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 larger $|B^+|\le(1+\nu)\cdot|B|$, and all distances between pairs in $X\
Externí odkaz:
http://arxiv.org/abs/2307.16612
Autor:
Shabat, Idan, Neiman, Ofer
Given an undirected graph $G=(V,E)$, an {\em $(\alpha,\beta)$-spanner} $H=(V,E')$ is a subgraph that approximately preserves distances; for every $u,v\in V$, $d_H(u,v)\le \alpha\cdot d_G(u,v)+\beta$. An $(\alpha,\beta)$-hopset is a graph $H=(V,E")$,
Externí odkaz:
http://arxiv.org/abs/2108.09673
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 spanners, so far little attention was given to weighted graphs. Only very rec
Externí odkaz:
http://arxiv.org/abs/2008.09877
Autor:
Elkin, Michael, Neiman, Ofer
Consider an undirected weighted graph $G = (V,E,w)$. We study the problem of computing $(1+\epsilon)$-approximate shortest paths for $S \times V$, for a subset $S \subseteq V$ of $|S| = n^r$ sources, for some $0 < r \le 1$. We devise a significantly
Externí odkaz:
http://arxiv.org/abs/2004.07572
Autor:
Elkin, Michael, Neiman, Ofer
Given an {\em unweighted} undirected graph $G = (V,E)$, and a pair of parameters $\epsilon > 0$, $\beta = 1,2,\ldots$, a subgraph $G' =(V,H)$, $H \subseteq E$, of $G$ is a {\em $(1+\epsilon,\beta)$-spanner} (aka, a {\em near-additive spanner}) of $G$
Externí odkaz:
http://arxiv.org/abs/2001.07477
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 paths} (ASP) for all pairs in $S \times V$ in both classical centraliz
Externí odkaz:
http://arxiv.org/abs/1907.11422
Autor:
Elkin, Michael, Neiman, Ofer
Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X \rightarrow Y$ is said to have a prioritized distortion $\alpha(\cdot)$, if for any pair $x_j,x'$ of distinct points in $X$, the distortion
Externí odkaz:
http://arxiv.org/abs/1907.06983