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

Christian Wulff-Nilsen

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

Datalogisk Institut

1488 Downloads (Pure)

Abstract

Vi betragter problemet med at finde Wiener-indekset af en graf, defineret som summen af afstande mellem alle grafens knudepar. Det er et åbent problem, om Wiener-indekset af en planar graf kan findes i subkvadratisk tid. Vi løser dette problem ved at præsentere en algoritme med O(n^2*log log n/log n) køretid og O(n) pladsforbrug, hvor n er antal knuder i grafen.

Originalsprog	Engelsk
Udgivelsessted	DIKU
Sider	1-10
Antal sider	10
Status	Udgivet - 2008

Adgang til dokumentet

08-11Forlagets udgivne version, 181 KB

Citationsformater

@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",

}

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 -

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

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater