Złożoność obliczania średniej odległości wykresu

Niech jest średnią odległość podłączonego wykresie $\rm{ad}(G)$ $G.$

Jeden sposób obliczenia jest przez sumowanie elementów macierz na odległość i skalowanie sumę odpowiednio. $\rm{ad}(G)$ $D(G),$ $G$

Jeśli grafem wyjściowym jest drzewo, to wiadomo, że średnią odległość można obliczyć w czasie liniowym (patrz B.Mohar, T.Pisanski - Jak obliczyć indeks Wienera na wykresie). Wydaje się, że istnieją szybkie algorytmy dla wykresów z ograniczoną szerokością drzewa.

Ciekawym pytaniem jest zatem, czy pomaga poznać Innymi słowy $D(G).$

Czy to możliwe, aby obliczyć w sub-kwadratowego czasu? $\rm{ad}(G)$

Chcę wiedzieć, czy istnieje teoretyczna dolna granica, dlaczego nie byłoby to możliwe.

cc.complexity-theory graph-theory graph-algorithms

— Jernej
źródło

Oprócz wspomnianego wyniku ograniczonej szerokości poprzecznej, o którym wspominasz (Cabello i Knauer, „Algorytmy dla wykresów ograniczonej szerokości poprzecznej poprzez wyszukiwanie zakresu ortogonalnego”, Comp. Geom. 2009), wiadomo, jak to szybko obliczyć dla wykresów osadzonych izometrycznie w kartezjańskich produktach drzew ( co okazuje się być istotne dla algorytmów graficznych) - patrz Yeh i Gutman, „Na sumę wszystkich odległości w grafach kompozytowych”, Discrete Math. 1994 oraz Chepoi i Klavžar, „Indeks Wienera i indeks Szegeda dla układów benzenoidowych w czasie liniowym”, JCICS 1997.

— David Eppstein

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

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

— dziewice
źródło