springerlink:10.1007/11602613_106
Summary
Gavoille, C. and Ly, O. (2005) Distance Labeling in Hyperbolic Graphs. In 16th International Symposium Algorithms and Computation (ISAAC), pages 1071-1079. . Springer Berlin / Heidelberg. ((URL))
Abstract
A graph {$G$} is {$\delta$}-hyperbolic if for any four vertices {$u , v , x , y$} of {$G$} the two larger of the three distance sums {$d_G( u , v ) + d_G ( x , y ), d_G ( u , x ) + d_G ( v , y ), d_G ( u , y ) + d_G ( v , x )$} differ by at most {$\delta$}, and the smallest {$\delta\geq 0$} for which {$G$} is {$\delta$}-hyperbolic is called the hyperbolicity of {$G$} . In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of {$G$} can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of {$O(\log^2 n )$} bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of {$O (\log n )$}. The label length is optimal for every additive error up to {$n^\varepsilon$}. We also show a lower bound of {$\Omega(\log\log n )$} on the approximation factor, namely every {$s$}-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires {$s = \Omega(\log\log n )$}. 11602613_106Bib
Bibtex entry
@INCOLLECTION { springerlink:10.1007/11602613_106,
AUTHOR = { Gavoille, C. and Ly, O. },
AFFILIATION = { LaBRI, Bordeaux University },
TITLE = { Distance Labeling in Hyperbolic Graphs },
BOOKTITLE = { 16th International Symposium Algorithms and Computation (ISAAC) },
SERIES = { Lecture Notes in Computer Science },
EDITOR = { Deng, Xiaotie and Du, Ding-Zhu },
PUBLISHER = { Springer Berlin / Heidelberg },
ISBN = { 978-3-540-30935-2 },
KEYWORD = { Computer Science },
PAGES = { 1071-1079 },
VOLUME = { 3827 },
URL = { http://dx.doi.org/10.1007/11602613_106 },
NOTE = { 10.1007/11602613_106 },
ABSTRACT = { A graph {$G$} is {$\delta$}-hyperbolic if for any four vertices {$u , v , x , y$} of {$G$} the two larger of the three distance sums {$d_G( u , v ) + d_G ( x , y ), d_G ( u , x ) + d_G ( v , y ), d_G ( u , y ) + d_G ( v , x )$} differ by at most {$\delta$}, and the smallest {$\delta\geq 0$} for which {$G$} is {$\delta$}-hyperbolic is called the hyperbolicity of {$G$} . In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of {$G$} can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of {$O(\log^2 n )$} bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of {$O (\log n )$}. The label length is optimal for every additive error up to {$n^\varepsilon$}. We also show a lower bound of {$\Omega(\log\log n )$} on the approximation factor, namely every {$s$}-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires {$s = \Omega(\log\log n )$}. },
YEAR = { 2005 },
}