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

Publikation: Working paper › Forskning

Standard

Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time. / Wulff-Nilsen, Christian.

DIKU, 2008. s. 1-10.

Publikation: Working paper › Forskning

Harvard

Wulff-Nilsen, C 2008 'Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time' DIKU, s. 1-10.

APA

Wulff-Nilsen, C. (2008). Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time. (s. 1-10).

Vancouver

Wulff-Nilsen C. Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time. DIKU. 2008, s. 1-10.

Author

Wulff-Nilsen, Christian. / Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time. DIKU, 2008. s. 1-10

Bibtex

@techreport{4fe081d0de5611ddb5fc000ea68e967b,
title = "Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time",
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.",
author = "Christian Wulff-Nilsen",
year = "2008",
language = "English",
pages = "1--10",
type = "WorkingPaper",

}

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