Abstract
We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label length and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different trade-offs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades.
More specifically, we present a distance labeling scheme with labels of length $\frac{\log 3}{2}n+o(n)$ bits\footnote{Throughout the paper, all logarithms are in base 2.} and constant decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size $(\log 3)n$ and $\Oh(n / \log n)$ decoding time, and Gavoille et al.\ (SODA'01), which uses labels of size $11n+o(n)$ and $O(\log\log n)$ decoding time. In addition, our algorithm is simpler than the previous ones.
In the case of integral edge weights of size at most $W$, we present almost matching upper and lower bounds for the label size $\ell$:
$\frac{1}{2}(n-1) \log \ceil{\frac{W}{2} + 1} \le \ell \le \frac{1}{2}n \log{(2W+1)} + O(\log n\cdot\log(nW))$.
Furthermore, for $r$-additive approximation labeling schemes, where distances can be off by up to an additive constant $r$, we present both upper and lower bounds. In particular, we present an upper bound for $1$-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency labeling scheme, namely $n/2$.
We also give results for bipartite graphs as well as for exact and $1$-additive distance oracles.
More specifically, we present a distance labeling scheme with labels of length $\frac{\log 3}{2}n+o(n)$ bits\footnote{Throughout the paper, all logarithms are in base 2.} and constant decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size $(\log 3)n$ and $\Oh(n / \log n)$ decoding time, and Gavoille et al.\ (SODA'01), which uses labels of size $11n+o(n)$ and $O(\log\log n)$ decoding time. In addition, our algorithm is simpler than the previous ones.
In the case of integral edge weights of size at most $W$, we present almost matching upper and lower bounds for the label size $\ell$:
$\frac{1}{2}(n-1) \log \ceil{\frac{W}{2} + 1} \le \ell \le \frac{1}{2}n \log{(2W+1)} + O(\log n\cdot\log(nW))$.
Furthermore, for $r$-additive approximation labeling schemes, where distances can be off by up to an additive constant $r$, we present both upper and lower bounds. In particular, we present an upper bound for $1$-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency labeling scheme, namely $n/2$.
We also give results for bipartite graphs as well as for exact and $1$-additive distance oracles.
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms |
| Antal sider | 13 |
| Forlag | Society for Industrial and Applied Mathematics |
| Publikationsdato | 2016 |
| Sider | 338-350 |
| ISBN (Trykt) | 978-1-611974-33-1 |
| Status | Udgivet - 2016 |
| Begivenhed | ACM-SIAM Symposium on Discrete Algorithms 2016 - Arlington, Virginia, USA Varighed: 10 jan. 2016 → 12 jan. 2016 |
Konference
| Konference | ACM-SIAM Symposium on Discrete Algorithms 2016 |
|---|---|
| Land/Område | USA |
| By | Arlington, Virginia |
| Periode | 10/01/2016 → 12/01/2016 |