Deterministic Decentralized Search in Random Graphs

DOI10.1007/978-3-540-77004-6_15MaRDI QIDQ5458311zbMATH OpenOpenAlexFDO

Authors E. Arcaute, Ning Chen, Ravi Kumar, David Liben-Nowell, Mohammad Mahdian, Hamid Nazerzadeh, Ying Xu

Publication date 11 April 2008

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.im/1259158601

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10)

Recommendations

• Deterministic Decentralized Search in Random Graphs
• Complex networks and decentralized search algorithms
• On the searchability of small-world networks with arbitrary underlying structure
• Non-searchability of random scale-free graphs
• Close to optimal decentralized routing in long-range contact networks

Cited in

(6)

• Decentralized search on spheres using small-world Markov chains: expected hitting times and structural properties
• Non-searchability of random scale-free graphs
• Deterministic Decentralized Search in Random Graphs
• Memoryless search algorithms in a network with faulty advice
• Local versus global search in channel graphs
• Complex networks and decentralized search algorithms

This page was built for publication: Deterministic Decentralized Search in Random Graphs

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