Universal augmentation schemes for network navigability

DOI10.1016/j.tcs.2008.12.061zbMath1168.68006OpenAlexW2023702603MaRDI QIDQ1019170

Cyril Gavoille, Pierre Fraigniaud, Adrian Kosowski, Zvi Lotker, Emmanuelle Lebhar

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.061

zbMATH Keywords

routinginformative labeling schemessmall world phenomenon

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Core Size and Densification in Preferential Attachment Networks, Kleinberg's grid unchained, Distance-based index structures for fast similarity search, Informational cost and networks navigability, Recovering the long-range links in augmented graphs, Graph Embedding through Random Walk for Shortest Paths Problems, Navigable small-world networks with few random bits, Sub-linear Universal Spatial Gossip Protocols, Low-Distortion Inference of Latent Similarities from a Multiplex Social Network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Graph minors. I. Excluding a forest
• A partial k-arboretum of graphs with bounded treewidth
• Could any graph be turned into a small-world?
• Tree-decompositions with bags of small diameter
• The small-world phenomenon
• Know thy neighbor's neighbor
• Graph Classes: A Survey
• Fault-tolerant routing in peer-to-peer systems
• Distance estimation and object location via rings of neighbors
• Object location using path separators
• Distributed Computing
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• Automata, Languages and Programming
• Algorithms – ESA 2005
• Eclecticism shrinks even small worlds
• Analyzing Kleinberg's (and other) small-world Models