The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs

Zylan Benjert, Kostas Lakis, Johannes Lengler +1

We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is $\Theta (\log n)$. This has strong implications for the runtime of many distrib…