Compact routing schemes in undirected and directed graphs

Abstract

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 $\approx 3.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 $\approx 3.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.