Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time
Research output: Working paper › Research
Standard
Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time. / Wulff-Nilsen, Christian.
DIKU, 2008. p. 1-10.Research output: Working paper › Research
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - UNPB
T1 - Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time
AU - Wulff-Nilsen, Christian
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
M3 - Working paper
SP - 1
EP - 10
BT - Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time
CY - DIKU
ER -
ID: 9617991