Greedy routing and the algorithmic small-world phenomenon

DOI10.1016/j.jcss.2021.11.003OpenAlexW4205236046MaRDI QIDQ2071825

Yannic Maus, Anisur Rahaman Molla, Karl Bringmann, Ralph Keusch, Johannes Lengler

Publication date: 31 January 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.05539

zbMATH Keywords

greedy routingrouting protocolssmall-world phenomenonrandom graph modelsreal-world networksInternet routing

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items

Graph distances in scale-free percolation: the logarithmic case

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Stability criteria and localization of the matrix spectrum in terms of trace functions
• Scale-free percolation
• Structures in supercritical scale-free percolation
• Geometric inhomogeneous random graphs
• Navigation in spatial networks: a survey
• Location-aided routing (LAR) in mobile ad hoc networks
• Distance estimation and object location via rings of neighbors
• Not all interventions are equal for the height of the second peak
• Greedy routing in small-world networks with power-law degrees
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Could any graph be turned into a small-world?
• Eclecticism shrinks even small worlds
• Upper and lower bounds for online routing on Delaunay triangulations
• On the searchability of small-world networks with arbitrary underlying structure
• Typical Distances in Ultrasmall Random Networks
• A Spatial Preferential Attachment Model with Local Clustering
• Clustering and the Hyperbolic Geometry of Complex Networks
• The Geometric Protean Model for On-Line Social Networks
• Statistical mechanics of complex networks
• The Structure of Geographical Threshold Graphs
• A Spatial Web Graph Model with Local Influence Regions
• Random Hyperbolic Graphs: Degree Sequence and Clustering
• The small-world phenomenon
• On the Diameter of Hyperbolic Random Graphs
• Networks Become Navigable as Nodes Move and Forget
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
• Know thy neighbor's neighbor
• Random Geometric Graphs
• Bootstrap percolation on geometric inhomogeneous random graphs
• Hyperbolic Random Graphs: Separators and Treewidth
• Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Object location using path separators
• A Bound for the Diameter of Random Hyperbolic Graphs
• The phase transition in inhomogeneous random graphs
• Greedy Routing and the Algorithmic Small-World Phenomenon
• Navigation in small-world networks: a scale-free continuum model
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• Navigating Low-Dimensional and Hierarchical Population Networks
• The average distances in random graphs with given expected degrees
• Algorithms – ESA 2005
• Analyzing Kleinberg's (and other) small-world Models