Know thy neighbor's neighbor

DOI10.1145/1007352.1007368zbMath1192.68048OpenAlexW2160405192MaRDI QIDQ3580959

Moni Naor, Gurmeet Singh Manku, Udi Wieder

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007368

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

D2B: A de Bruijn based content-addressable network, Could any graph be turned into a small-world?, Eclecticism shrinks even small worlds, Degree-optimal routing for P2P systems, The expansion and mixing time of skip graphs with applications, Kleinberg's grid unchained, The forgiving graph: a distributed data structure for low stretch under adversarial attack, Distance estimation and object location via rings of neighbors, Depth of Field and Cautious-Greedy Routing in Social Networks, F-Chord: Improved uniform routing on Chord, \(D^2\)-tree: a new overlay with deterministic bounds, A model of self‐avoiding random walks for searching complex networks, Neighbor selection and hitting probability in small-world graphs, Recovering the long-range links in augmented graphs, Greedy routing in small-world networks with power-law degrees, Routing complexity of faulty networks, Navigation in spatial networks: a survey, Optimal routing in a small-world network, Universal augmentation schemes for network navigability, Greedy routing and the algorithmic small-world phenomenon, Navigable small-world networks with few random bits, Low-Distortion Inference of Latent Similarities from a Multiplex Social Network, Close to optimal decentralized routing in long-range contact networks