Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for this?
average distance in a graph
1
$\begingroup$
algorithms
graph-theory
computational-complexity