Additive spanners and distance and routing labeling schemes for hyperbolic graphs
From MaRDI portal
Publication:2428695
DOI10.1007/S00453-010-9478-XzbMath1239.05048OpenAlexW2141663929MaRDI QIDQ2428695
Victor Chepoi, Bertrand Estellon, Yang Xiang, Yann Vaxès, Feodor F. Dragan, Michel A. Habib
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
Geometric group theory (20F65) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items (19)
Obstructions to a small hyperbolicity in Helly graphs ⋮ How to use spanning trees to navigate in graphs ⋮ On Computing the Hyperbolicity of Real-World Graphs ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ Why did the shape of your network change? (On detecting network anomalies via non-local curvatures) ⋮ Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane ⋮ On the hyperbolicity of random graphs ⋮ Navigating the negative curvature of Google Maps ⋮ Implicit representation of relations ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ A review of two network curvature measures ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ On Computing the Gromov Hyperbolicity ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Fellow travelers phenomenon present in real-world networks ⋮ Mathematical properties on the hyperbolicity of interval graphs ⋮ Computing the Gromov hyperbolicity of a discrete metric space
Cites Work
- 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
- Proximity-preserving labeling schemes
- 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
This page was built for publication: Additive spanners and distance and routing labeling schemes for hyperbolic graphs
