Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth

Karl Bringmann, Thore Husfeldt, Måns Magnusson

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\cdot \binom{k+\lcei…