Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs

作者：Chepoi Victor; Dragan Feodor F^*; Estellon Bertrand; Habib Michel; Vaxes Yann; Xiang Yang

来源：Algorithmica, 2012, 62(3-4): 713-732.

DOI：10.1007/s00453-010-9478-x

• Algorithms
• Distance and routing labeling schemes
• Additive spanners
• delta-Hyperbolic graphs

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 a parts per thousand yen1/2 has an additive O(delta 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 a parts per thousand yen1/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.

• 出版日期2012-4