Greedy routing and the algorithmic small-world phenomenon
From MaRDI portal
Publication:2071825
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
greedy routingrouting protocolssmall-world phenomenonrandom graph modelsreal-world networksInternet routing
Related Items
Uses Software
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
