Abstract
We solve three open problems: the existence of subquadratic time algorithms for computing the Wiener index (sum of APSP distances) and the diameter (maximum distance between any vertex pair) of a planar graph with non-negative edge weights and the stretch factor of a plane geometric graph (maximum over all pairs of distinct vertices of the ratio between the graph distance and the Euclidean distance between the two vertices). More specifically, we show that the Wiener index and diameter can be found in O(n^2*(log log n)^4/log n) worst-case time and that the stretch factor can be found in O(n^2*(log log n)^4/log n) expected time, where n is the number of vertices. We also show how to compute the Wiener index and diameter of an unweighted n-vertex subgraph-closed n^{0.5}-separable graph in O(n^2*log log n/log n) worst-case time and with O(n) space.
| Original language | English |
|---|---|
| Place of Publication | København |
| Publisher | Department of Computer Science, University of Copenhagen |
| Number of pages | 30 |
| Publication status | Published - 2008 |