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

Publikation: Working paperForskning

Standard

Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. / Wulff-Nilsen, Christian.

København : Department of Computer Science, University of Copenhagen, 2008.

Publikation: Working paperForskning

Harvard

Wulff-Nilsen, C 2008 'Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time' Department of Computer Science, University of Copenhagen, København.

APA

Wulff-Nilsen, C. (2008). Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. København: Department of Computer Science, University of Copenhagen.

Vancouver

Wulff-Nilsen C. Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. København: Department of Computer Science, University of Copenhagen. 2008.

Author

Wulff-Nilsen, Christian. / Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. København : Department of Computer Science, University of Copenhagen, 2008.

Bibtex

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

}

RIS

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 -

ID: 9618617