کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414762 | 681030 | 2013 | 8 صفحه PDF | دانلود رایگان |

Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o(n2)o(n2) time. We show that both problems can be solved in O(n2loglogn/logn) time with O(n)O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G . More generally, for any parameter S∈[(logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.
Journal: Computational Geometry - Volume 46, Issue 7, October 2013, Pages 831–838