Deterministic Decentralized Search in Random Graphs

DOI10.1007/978-3-540-77004-6_15zbMATH Open1136.68318OpenAlexW2080930003MaRDI QIDQ5458311FDOQ5458311

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

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

Mathematics Subject Classification ID

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

Cited In (6)

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

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)