Close to optimal decentralized routing in long-range contact networks

DOI10.1016/J.TCS.2005.09.019MaRDI QIDQ2581272zbMATH OpenOpenAlexFDO

Authors 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

random graph modelrouting algorithmsmall world

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Automata, Languages and Programming
• scientific article; zbMATH DE number 2006658
• The small-world phenomenon: an algorithmic perspective
• Efficient routeing in Poisson small-world networks
• Optimal routing in a small-world network

Cites work

• Analyzing Kleinberg's (and other) small-world models
• Collective dynamics of `small-world' networks
• Eclecticism shrinks even small worlds
• Fault-tolerant routing in peer-to-peer systems
• Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet
• scientific article; zbMATH DE number 2006658 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
• The Diameter of a Cycle Plus a Random Matching
• The diameter of a long-range percolation graph
• The diameter of long-range percolation clusters on finite cycles
• The small-world phenomenon: an algorithmic perspective
• The Structure and Function of Complex Networks

Cited in

(15)

• Navigable small-world networks with few random bits
• Navigation in spatial networks: a survey
• Greedy routing and the algorithmic small-world phenomenon
• On the searchability of small-world networks with arbitrary underlying structure
• The small-world phenomenon: an algorithmic perspective
• Networks Become Navigable as Nodes Move and Forget
• Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
• Decentralized search on spheres using small-world Markov chains: expected hitting times and structural properties
• scientific article; zbMATH DE number 2006658 (Why is no real title available?)
• Low-distortion inference of latent similarities from a multiplex social network
• Depth of Field and Cautious-Greedy Routing in Social Networks
• Optimal path search in small worlds, dimension matters
• Navigating Low-Dimensional and Hierarchical Population Networks
• Deterministic Decentralized Search in Random Graphs
• Automata, Languages and Programming

Describes a project that uses

Uses Software

• Chord

This page was built for publication: Close to optimal decentralized routing in long-range contact networks

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