Complexité du calcul de la distance moyenne d'un graphe

Soit représente la distance moyenne d'un graphe connexe G $\rm{ad}(G)$$G.$

Une façon de calculer est de résumer les éléments de D ( G ) , la matrice de distance de G et de mettre à l'échelle la somme de manière appropriée.$\rm{ad}(G)$$D(G),$$G$

Si le graphique de sortie est un arbre, il est connu que la distance moyenne peut être calculée en temps linéaire (voir B.Mohar, T.Pisanski - Comment calculer l'indice de Wiener d'un graphique). Il semble qu'il existe également des algorithmes rapides pour les graphiques avec une largeur d'arbre bornée.

Une question intéressante est donc de savoir si cela aide à connaître En d'autres termes$D(G).$

Est-il possible de calculer en temps sub-quadratique?$\rm{ad}(G)$

Ce que je voudrais savoir, c'est s'il existe une limite inférieure théorique pour expliquer pourquoi cela ne serait pas possible.

$O(n^{2-\delta})$$\delta>0$$\tilde{O}(n)$$n$$n$$O(2^{(1-\varepsilon)n})$

$2-M/{N\choose 2}$$N$$M$