2005 | OriginalPaper | Chapter
Distance Labeling in Hyperbolic Graphs
Authors : Cyril Gavoille, Olivier Ly
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A graph
G
is
δ
-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
δ
, and the smallest
δ
≥ 0 for which
G
is
δ
-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
ε
. We also show a lower bound of Ω(log log
n
) on the approximation factor, namely every
s
-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires
s
= Ω(log log
n
).