Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

Christian Wulff-Nilsen

Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

Datalogisk Institut

1853 Downloads (Pure)

Abstract

Vi løser tre åbne problemer ved at bevise eksistensen af algoritmer med subkvadratisk køretid til at bestemme Wiener-indekset (summen af APSP-afstande) og diameteren (maksimal afstand mellem knudepar) af en planar graf med ikke-negative kantvægte samt stretch-faktoren af en plan geometrisk graf (maksimum over alle par af forskellige knuder af forholdet mellem graf-afstanden og den Euklidiske afstand mellem de to knuder). Mere præcist viser vi, at Wiener-indekset og diameteren kan bestemmes i O(n^2*(log log n)^4/log n) worst-case-tid, og at stretch-faktoren kan bestemmes i O(n^2*(log log n)^4/log n) forventet tid, hvor n er antallet af knuder. Vi viser også, hvordan man kan bestemme Wiener-indekset og diameteren af en ikke-vægtet delgraf-afsluttet n^{0.5}-separabel graf i O(n^2*log log n/log n) worst-case-tid og O(n) plads.

Originalsprog	Engelsk
Udgivelsessted	København
Udgiver	Department of Computer Science, University of Copenhagen
Antal sider	30
Status	Udgivet - 2008

Adgang til dokumentet

08-16Forlagets udgivne version, 368 KB

Citationsformater

@techreport{f9f34bf0de5911ddb5fc000ea68e967b,

title = "Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time",

abstract = "We solve three open problems: the existence of subquadratic time algorithms for computing the Wiener index (sum of APSP distances) and the diameter (maximum distance between any vertex pair) of a planar graph with non-negative edge weights and the stretch factor of a plane geometric graph (maximum over all pairs of distinct vertices of the ratio between the graph distance and the Euclidean distance between the two vertices). More specifically, we show that the Wiener index and diameter can be found in O(n^2*(log log n)^4/log n) worst-case time and that the stretch factor can be found in O(n^2*(log log n)^4/log n) expected time, where n is the number of vertices. We also show how to compute the Wiener index and diameter of an unweighted n-vertex subgraph-closed n^{0.5}-separable graph in O(n^2*log log n/log n) worst-case time and with O(n) space.",

author = "Christian Wulff-Nilsen",

year = "2008",

language = "English",

publisher = "Department of Computer Science, University of Copenhagen",

type = "WorkingPaper",

institution = "Department of Computer Science, University of Copenhagen",

}

TY - UNPB

T1 - Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

AU - Wulff-Nilsen, Christian

PY - 2008

Y1 - 2008

N2 - We solve three open problems: the existence of subquadratic time algorithms for computing the Wiener index (sum of APSP distances) and the diameter (maximum distance between any vertex pair) of a planar graph with non-negative edge weights and the stretch factor of a plane geometric graph (maximum over all pairs of distinct vertices of the ratio between the graph distance and the Euclidean distance between the two vertices). More specifically, we show that the Wiener index and diameter can be found in O(n^2*(log log n)^4/log n) worst-case time and that the stretch factor can be found in O(n^2*(log log n)^4/log n) expected time, where n is the number of vertices. We also show how to compute the Wiener index and diameter of an unweighted n-vertex subgraph-closed n^{0.5}-separable graph in O(n^2*log log n/log n) worst-case time and with O(n) space.

AB - We solve three open problems: the existence of subquadratic time algorithms for computing the Wiener index (sum of APSP distances) and the diameter (maximum distance between any vertex pair) of a planar graph with non-negative edge weights and the stretch factor of a plane geometric graph (maximum over all pairs of distinct vertices of the ratio between the graph distance and the Euclidean distance between the two vertices). More specifically, we show that the Wiener index and diameter can be found in O(n^2*(log log n)^4/log n) worst-case time and that the stretch factor can be found in O(n^2*(log log n)^4/log n) expected time, where n is the number of vertices. We also show how to compute the Wiener index and diameter of an unweighted n-vertex subgraph-closed n^{0.5}-separable graph in O(n^2*log log n/log n) worst-case time and with O(n) space.

M3 - Working paper

BT - Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

PB - Department of Computer Science, University of Copenhagen

CY - København

ER -

Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater