A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability

DOI10.1007/11841036_35zbMath1131.68486OpenAlexW2137994750MaRDI QIDQ5449543

Pierre Fraigniaud, Zvi Lotker, Emmanuelle Lebhar

Publication date: 11 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11841036_35

zbMATH Keywords

doubling dimensiongreedy routingsmall world

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Demand-aware network designs of bounded degree ⋮ Distance estimation and object location via rings of neighbors ⋮ Depth of Field and Cautious-Greedy Routing in Social Networks ⋮ Content Search through Comparisons ⋮ Recovering the long-range links in augmented graphs ⋮ Universal augmentation schemes for network navigability ⋮ Greedy routing and the algorithmic small-world phenomenon ⋮ Navigable small-world networks with few random bits ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network

This page was built for publication: A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability