Skip to main content

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.

search-config
loading …

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

).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Distance Labeling in Hyperbolic Graphs
verfasst von
Cyril Gavoille
Olivier Ly
Copyright-Jahr
2005
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/11602613_106