Multivariate Analysis of Orthogonal Range Searching and Graph Distances
We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time O(n·(k+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n1 + ϵexp O(k) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discret