Tight lower bounds for greedy routing in uniform small world rings

DOI10.1145/1536414.1536494zbMath1304.68014OpenAlexW2081963068MaRDI QIDQ5172754

Martin Dietzfelbinger, Philipp Woelfel

Publication date: 4 February 2015

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

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

zbMATH Keywords

random graphslower boundgreedy routingpeer-to-peersmall world graphssmall worlds

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)

Related Items (1)

Greedy routing in small-world networks with power-law degrees

This page was built for publication: Tight lower bounds for greedy routing in uniform small world rings