2005 | OriginalPaper | Buchkapitel
Distance Labeling in Hyperbolic Graphs
verfasst von : Cyril Gavoille, Olivier Ly
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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
).