Abstract
We consider the problem of computing the Wiener index of a graph, defined as the sum of distances between all pairs of its vertices. It is an open problem whether the Wiener index of a planar graph can be found in subquadratic time. We solve this problem by presenting an algorithm with O(n^2*log log n/log n) running time and O(n) space requirement where n is the number of vertices of the graph.
| Original language | English |
|---|---|
| Place of Publication | DIKU |
| Pages | 1-10 |
| Number of pages | 10 |
| Publication status | Published - 2008 |