Diameter Computation on (Random) Geometric Graphs

Thomas Bläsius, Annemarie Schaub, Marcus Wilhelm

We present an algorithm that computes the diameter of random geometric graphs (RGGs) with expected average degree $\hat{I}˜(n^{\hat{I}}´)$ for constant $\hat{I}´\in (0,1)$ in $\tilde{O}(n^{\frac{3}{2}(…