Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time

Research output: Working paperResearch

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 languageEnglish
Place of PublicationDIKU
Pages1-10
Number of pages10
Publication statusPublished - 2008

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 9617991