Close to optimal decentralized routing in long-range contact networks

DOI10.1016/j.tcs.2005.09.019zbMath1081.68001MaRDI QIDQ2581272

Emmanuelle Lebhar, Nicolas Schabanel

Publication date: 9 January 2006

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

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

zbMATH Keywords

routing algorithm; small world; random graph model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C80: Random graphs (graph-theoretic aspects)

68W05: Nonnumerical algorithms

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

Related Items

Low-Distortion Inference of Latent Similarities from a Multiplex Social Network, Navigable small-world networks with few random bits

Uses Software

• Chord

Cites Work

• Unnamed Item
• Unnamed Item
• Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet
• The diameter of long-range percolation clusters on finite cycles
• The diameter of a long-range percolation graph
• The small-world phenomenon
• Know thy neighbor's neighbor
• The Diameter of a Cycle Plus a Random Matching
• The Structure and Function of Complex Networks
• Fault-tolerant routing in peer-to-peer systems
• Collective dynamics of ‘small-world’ networks
• Eclecticism shrinks even small worlds
• Analyzing Kleinberg's (and other) small-world Models