Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.13753 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916926640357376 |
|---|---|
| author | Kadria, Avi Roditty, Liam |
| author_facet | Kadria, Avi Roditty, Liam |
| contents | In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs.
\textit{For weighted undirected graphs}, more than a decade ago, Chechik [PODC'13] presented a $\approx3.68k$-stretch compact routing scheme that uses $\tilde{O}(n^{1/k}\log{D})$ local storage, where $D$ is the normalized diameter, for every $k>1$. We present a $\approx 2.64k$-stretch compact routing scheme that uses $\tilde{O}(n^{1/k})$ local storage \textit{on average} in each vertex. This is the first compact routing scheme that uses total local storage of $\tilde{O}(n^{1+1/k})$ while achieving a $c \cdot k$ stretch, for a constant $c < 3$.
In real-world network protocols, messages are usually transformed as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a $(4k-5)$-stretch path, and the rest of the communication session is routed along an optimal $(2k-1)$-stretch path. It is straightforward to improve the $(4k-5)$-stretch of the handshake to $\approx3.68k$-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal $(2k-1)$, by borrowing the concept of roundtrip routing from directed graphs to \textit{undirected} graphs.
\textit{For weighted directed graphs}, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a $(4k+\eps)$-stretch compact roundtrip routing scheme that uses $\tilde{O}(n^{1/k})$ local storage for every $k\ge 3$. For $k=3$, this gives a $(12+\eps)$-roundtrip stretch using $\tilde{O}(n^{1/3})$ local storage. We improve the stretch by developing a $7$-roundtrip stretch routing scheme with $\tilde{O}(n^{1/3})$ local storage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13753 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Compact routing schemes in undirected and directed graphs Kadria, Avi Roditty, Liam Networking and Internet Architecture In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. \textit{For weighted undirected graphs}, more than a decade ago, Chechik [PODC'13] presented a $\approx3.68k$-stretch compact routing scheme that uses $\tilde{O}(n^{1/k}\log{D})$ local storage, where $D$ is the normalized diameter, for every $k>1$. We present a $\approx 2.64k$-stretch compact routing scheme that uses $\tilde{O}(n^{1/k})$ local storage \textit{on average} in each vertex. This is the first compact routing scheme that uses total local storage of $\tilde{O}(n^{1+1/k})$ while achieving a $c \cdot k$ stretch, for a constant $c < 3$. In real-world network protocols, messages are usually transformed as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a $(4k-5)$-stretch path, and the rest of the communication session is routed along an optimal $(2k-1)$-stretch path. It is straightforward to improve the $(4k-5)$-stretch of the handshake to $\approx3.68k$-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal $(2k-1)$, by borrowing the concept of roundtrip routing from directed graphs to \textit{undirected} graphs. \textit{For weighted directed graphs}, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a $(4k+\eps)$-stretch compact roundtrip routing scheme that uses $\tilde{O}(n^{1/k})$ local storage for every $k\ge 3$. For $k=3$, this gives a $(12+\eps)$-roundtrip stretch using $\tilde{O}(n^{1/3})$ local storage. We improve the stretch by developing a $7$-roundtrip stretch routing scheme with $\tilde{O}(n^{1/3})$ local storage. |
| title | Compact routing schemes in undirected and directed graphs |
| topic | Networking and Internet Architecture |
| url | https://arxiv.org/abs/2503.13753 |