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
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
