Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Cohen, Sarel"'
Autor:
Bilò, Davide, Chechik, Shiri, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Schirneck, Martin
A distance oracle (DO) with stretch $(\alpha, \beta)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$, returns a value $\widehat{d}(s,t)$ such that $d(s,t) \le \widehat{d}(s,t) \le \alpha \cdot d(s,t) + \beta$. An $f$
Externí odkaz:
http://arxiv.org/abs/2408.10014
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph $G=(V,E,w)$, where $V=\{r\}\cup S \cup T$, and an integer $k$, the goal is to find a minimum cost subgraph of $G$ in which there are $k$ edge-d
Externí odkaz:
http://arxiv.org/abs/2407.07543
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. T
Externí odkaz:
http://arxiv.org/abs/2402.05534
Autor:
Bilò, Davide, Chechik, Shiri, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Schirneck, Martin
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stre
Externí odkaz:
http://arxiv.org/abs/2307.11677
Autor:
Bilò, Davide, Chechik, Shiri, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Krogmann, Simon, Schirneck, Martin
Publikováno v:
TheoretiCS, Volume 3 (June 5, 2024) theoretics:11689
An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\sigma \ge 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a
Externí odkaz:
http://arxiv.org/abs/2305.11580
Autor:
Bilò, Davide, Cohen, Sarel, Friedrich, Tobias, Gawendowicz, Hans, Klodt, Nicolas, Lenzner, Pascal, Skretas, George
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are on
Externí odkaz:
http://arxiv.org/abs/2305.07494
Autor:
Bilò, Davide, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Krogmann, Simon, Schirneck, Martin
We study the problem of estimating the $ST$-diameter of a graph that is subject to a bounded number of edge failures. An $f$-edge fault-tolerant $ST$-diameter oracle ($f$-FDO-$ST$) is a data structure that preprocesses a given graph $G$, two sets of
Externí odkaz:
http://arxiv.org/abs/2305.03697
Autor:
Bilò, Davide, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Krogmann, Simon, Schirneck, Martin
An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\sigma \geq 1$ is a data structure that preprocesses an input graph $G$. When queried with the triple $(s,t,F)$, where $s, t \in V$ and $F \subseteq E$ contains at most $f$
Externí odkaz:
http://arxiv.org/abs/2304.14184
Autor:
Jeong, Davin, Gunby-Mann, Allison, Cohen, Sarel, Katzmann, Maximilian, Pham, Chau, Bhakta, Arnav, Friedrich, Tobias, Chin, Sang
One of the most fundamental graph problems is finding a shortest path from a source to a target node. While in its basic forms the problem has been studied extensively and efficient algorithms are known, it becomes significantly harder as soon as par
Externí odkaz:
http://arxiv.org/abs/2211.02681
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccen
Externí odkaz:
http://arxiv.org/abs/2204.10679