Eclecticism shrinks even small worlds

DOI10.1145/1011767.1011793zbMath1321.05246OpenAlexW2005719338MaRDI QIDQ5501496

Christophe Paul, Pierre Fraigniaud, Cyril Gavoille

Publication date: 3 August 2015

Published in: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.396.5656

zbMATH Keywords

routingsmall world graphsdistributed hash tables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

D2B: A de Bruijn based content-addressable network ⋮ Could any graph be turned into a small-world? ⋮ Distance estimation and object location via rings of neighbors ⋮ Asymptotically optimal solutions for small world graphs ⋮ Depth of Field and Cautious-Greedy Routing in Social Networks ⋮ Recovering the long-range links in augmented graphs ⋮ Greedy routing in small-world networks with power-law degrees ⋮ Navigation in spatial networks: a survey ⋮ Optimal routing in a small-world network ⋮ Universal augmentation schemes for network navigability ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network ⋮ Close to optimal decentralized routing in long-range contact networks

This page was built for publication: Eclecticism shrinks even small worlds