Additive spanners and distance and routing labeling schemes for hyperbolic graphs
From MaRDI portal
Publication:2428695
DOI10.1007/s00453-010-9478-xzbMath1239.05048MaRDI QIDQ2428695
Feodor F. Dragan, Yann Vaxès, Victor Chepoi, Yang Xiang, Michel A. Habib, Bertrand Estellon
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9478-x
20F65: Geometric group theory
05C12: Distance in graphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
Related Items
On the hyperbolicity of random graphs, How to use spanning trees to navigate in graphs, Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Collective tree spanners in graphs with bounded parameters
- Gromov hyperbolicity of Denjoy domains
- Localized and compact data-structure for comparability graphs
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- Query efficient implementation of graphs of bounded clique-width
- Distance labeling scheme and split decomposition
- The Hilbert metric and Gromov hyperbolicity.
- A note on distance approximating trees in graphs
- Hyperbolic bridged graphs
- Distance estimation and object location via rings of neighbors
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Compact Routing with Minimum Stretch
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- Distance and routing labeling schemes for non-positively curved plane graphs
- Dynamic Routing and Location Services in Metrics of Low Doubling Dimension
- Approximate distance oracles
- Bypassing the embedding
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- 1-Hyperbolic Graphs
- Distributed Computing: A Locality-Sensitive Approach
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- Compact routing schemes with low stretch factor
- Distance labeling in graphs
- Object location using path separators
- Optimal-stretch name-independent compact routing in doubling metrics
- Excluded minors, network decomposition, and multicommodity flow
- Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
- Collective Tree Spanners and Routing in AT-free Related Graphs
- Reconstructing approximate tree metrics
- Compact routing with slack in low doubling dimension
- Compact oracles for reachability and approximate distances in planar digraphs
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Labeling Schemes for Small Distances in Trees
- Collective tree spanners of graphs
- Algorithms and Computation
- Space-efficiency for routing schemes of stretch factor three