Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time
Research output: Working paper › Research
Documents
- 08-11
Final published version, 181 KB, PDF document
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 |
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 9617991