All-Hops Shortest Paths
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917823999115264 |
|---|---|
| author | Williams, Virginia Vassilevska Xi, Zoe Xu, Yinzhan Zwick, Uri |
| author_facet | Williams, Virginia Vassilevska Xi, Zoe Xu, Yinzhan Zwick, Uri |
| contents | Let $G=(V,E,w)$ be a weighted directed graph without negative cycles. For two vertices $s,t\in V$, we let $d_{\le h}(s,t)$ be the minimum, according to the weight function $w$, of a path from $s$ to $t$ that uses at most $h$ edges, or hops. We consider algorithms for computing $d_{\le h}(s,t)$ for every $1\le h\le n$, where $n=|V|$, in various settings. We consider the single-pair, single-source and all-pairs versions of the problem. We also consider a distance oracle version of the problem in which we are not required to explicitly compute all distances $d_{\le h}(s,t)$, but rather return each one of these distances upon request. We consider both the case in which the edge weights are arbitrary, and in which they are small integers in the range $\{-M,\ldots,M\}$. For some of our results we obtain matching conditional lower bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23617 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | All-Hops Shortest Paths Williams, Virginia Vassilevska Xi, Zoe Xu, Yinzhan Zwick, Uri Data Structures and Algorithms Let $G=(V,E,w)$ be a weighted directed graph without negative cycles. For two vertices $s,t\in V$, we let $d_{\le h}(s,t)$ be the minimum, according to the weight function $w$, of a path from $s$ to $t$ that uses at most $h$ edges, or hops. We consider algorithms for computing $d_{\le h}(s,t)$ for every $1\le h\le n$, where $n=|V|$, in various settings. We consider the single-pair, single-source and all-pairs versions of the problem. We also consider a distance oracle version of the problem in which we are not required to explicitly compute all distances $d_{\le h}(s,t)$, but rather return each one of these distances upon request. We consider both the case in which the edge weights are arbitrary, and in which they are small integers in the range $\{-M,\ldots,M\}$. For some of our results we obtain matching conditional lower bounds. |
| title | All-Hops Shortest Paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.23617 |