Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth
share
The inverse geodesic length of a graph G is the sum of the inverse of the distances between all pairs of distinct vertices of G. In some domains it is known as the Harary index or the global efficiency of the graph. We show that, if G is planar and has n vertices, then the inverse geodesic length of G can be computed in roughly O(n^9/5) time. We also show that, if G has n vertices and treewidth at most k, then the inverse geodesic length of G can be computed in O(n log^O(k)n) time. In both cases we use techniques developed for computing the sum of the distances, which does not have “inverse” component, together with batched evaluations of rational functions.
READ FULL TEXT