Summary

Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vaxès, Y. and Xiang, Y. (2012) Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs. Algorithmica, 62:713-732. ((URL))

Abstract

{$\delta$}-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points {$u , v , w , x$} , the two larger of the distance sums {$d ( u , v )+ d ( w , x ), d ( u , w )+ d ( v , x ), d ( u , x )+ d ( v , w )$} differ by at most {$2\delta$}. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted {$\delta$}-hyperbolic graphs. Using the Layering Partition technique, we show that every {$n$}-vertex {$\delta$}-hyperbolic graph with {$\delta\geq 1/2$} has an additive {$O (\delte\log n )$}-spanner with at most {$O (\delta n )$} edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of {$\delta$}-hyperbolic graphs with an additive error {$O ( \delta\log n )$}. The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of {$n$}-vertex {$\delta$}-hyperbolic graphs with {$\delta\geq 1/2$} admits a routing labeling scheme with {$O ( \delta\log^2 n )$} bit labels, {$O ( \delta\log n )$} additive stretch and {$O (\log^2 (4 \delta ))$} time routing protocol, and a distance labeling scheme with {$O (\log^2 n )$} bit labels, {$O ( \delta \log n )$} additive error and constant time distance decoder. s00453-010-9478-xBib

Bibtex entry

AUTHOR = { Chepoi, V. and Dragan, F. and Estellon, B. and Habib, M. and Vaxès, Y. and Xiang, Y. },
AFFILIATION = { Laboratoire d’Informatique Fondamentale, Faculté des Sciences de Luminy, Université de la Mediterranée, Marseille, 13288 Marseille Cedex 9, France },
TITLE = { Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs },
JOURNAL = { Algorithmica },
PUBLISHER = { Springer New York },
ISSN = { 0178-4617 },
KEYWORD = { Computer Science },
PAGES = { 713-732 },
VOLUME = { 62 },
ISSUE = { 3 },
URL = { http://dx.doi.org/10.1007/s00453-010-9478-x },
NOTE = { 10.1007/s00453-010-9478-x },
ABSTRACT = { {$\delta$}-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points {$u , v , w , x$} , the two larger of the distance sums {$d ( u , v )+ d ( w , x ), d ( u , w )+ d ( v , x ), d ( u , x )+ d ( v , w )$} differ by at most {$2\delta$}. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted {$\delta$}-hyperbolic graphs. Using the Layering Partition technique, we show that every {$n$}-vertex {$\delta$}-hyperbolic graph with {$\delta\geq 1/2$} has an additive {$O (\delte\log n )$}-spanner with at most {$O (\delta n )$} edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of {$\delta$}-hyperbolic graphs with an additive error {$O ( \delta\log n )$}. The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of {$n$}-vertex {$\delta$}-hyperbolic graphs with {$\delta\geq 1/2$} admits a routing labeling scheme with {$O ( \delta\log^2 n )$} bit labels, {$O ( \delta\log n )$} additive stretch and {$O (\log^2 (4 \delta ))$} time routing protocol, and a distance labeling scheme with {$O (\log^2 n )$} bit labels, {$O ( \delta \log n )$} additive error and constant time distance decoder. },
YEAR = { 2012 },
}