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 (23)

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

This page was built for publication: Know thy neighbor's neighbor