Simpler, faster and shorter labels for distances in graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Simpler, faster and shorter labels for distances in graphs. / Alstrup, Stephen; Gavoille, Cyril; Halvorsen, Esben Bistrup; Petersen, Holger.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2016. p. 338-350.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Simpler, faster and shorter labels for distances in graphs
AU - Alstrup, Stephen
AU - Gavoille, Cyril
AU - Halvorsen, Esben Bistrup
AU - Petersen, Holger
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
M3 - Article in proceedings
SN - 978-1-611974-33-1
SP - 338
EP - 350
BT - Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Society for Industrial and Applied Mathematics
Y2 - 10 January 2016 through 12 January 2016
ER -
ID: 167584690