Hyperbolic Embeddings for Near-Optimal Greedy Routing

DOI10.1145/3381751MaRDI QIDQ6039932zbMATH OpenOpenAlexWikidataFDO

Authors Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer

Publication date 23 May 2023

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3381751

zbMATH Keywords

geographic routinggreedy routinghyperbolic spacerobustnessspanning treesstretch

Mathematics Subject Classification ID

Elementary problems in hyperbolic and elliptic geometries (51M09) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Hyperbolic Embeddings for Near-Optimal Greedy Routing
• Greedy routing via embedding graphs onto semi-metric spaces
• Greedy Routing via Embedding Graphs onto Semi-metric Spaces
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• Succinct greedy geometric routing in the Euclidean plane
• An optimal greedy routing algorithm for triangulated polygons
• Tight lower bounds for greedy routing in higher-dimensional small-world grids
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• Efficient shortest paths in scale-free networks with underlying hyperbolic geometry
• Greedy routing in circulant networks

Cites work

• Efficient embedding of scale-free graphs in the hyperbolic plane
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• KADABRA is an adaptive algorithm for betweenness via random approximation
• Low distortion Delaunay embedding of trees in hyperbolic plane
• MPFR
• Navigation in real-world complex networks through embedding in latent spaces
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry

Cited in

(11)

• Hydra: a method for strain-minimizing hyperbolic embedding of network- and distance-based data
• Space lower bounds for low-stretch greedy embeddings
• Greedy Routing via Embedding Graphs onto Semi-metric Spaces
• An improved hyperbolic embedding algorithm
• Graph Embedding through Random Walk for Shortest Paths Problems
• Efficient embedding of scale-free graphs in the hyperbolic plane
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• Navigation in networks by the Bolyai-Lobachevsky hyperbolic geometry
• Hyperbolic Embeddings for Near-Optimal Greedy Routing
• Improved bounds for graph distances in scale free percolation and related models
• Space lower bounds for low-stretch greedy embeddings

This page was built for publication: Hyperbolic Embeddings for Near-Optimal Greedy Routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039932)