Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

Christian Wulff-Nilsen

doi:10.1016/j.comgeo.2012.01.016

Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

3 Citationer (Scopus)

Abstract

Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o(ⁿ²) time. We show that both problems can be solved in O( ⁿ²loglogn/logn) time with O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G. More generally, for any parameter Sâ̂̂[( ^{logn/loglogn)2},n2^/5], distance queries can be answered in O(SlogS/logn) time per query with O(ⁿ²/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.

Originalsprog	Engelsk
Tidsskrift	Computational Geometry
Vol/bind	46
Udgave nummer	7
Sider (fra-til)	831-838
Antal sider	8
ISSN	0925-7721
DOI	https://doi.org/10.1016/j.comgeo.2012.01.016
Status	Udgivet - 2013
Udgivet eksternt	Ja

Adgang til dokumentet

10.1016/j.comgeo.2012.01.016

Citationsformater

@article{6fb5c66ccf8245e6a5a35feeb0730a5e,

title = "Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time",

abstract = "Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o(n2) time. We show that both problems can be solved in O( n2loglogn/logn) time with O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G. More generally, for any parameter S{\^a}{\^̂}[( logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.",

author = "Christian Wulff-Nilsen",

note = "EuroCG 2009",

year = "2013",

doi = "10.1016/j.comgeo.2012.01.016",

language = "English",

volume = "46",

pages = "831--838",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

AU - Wulff-Nilsen, Christian

N1 - EuroCG 2009

PY - 2013

Y1 - 2013

N2 - Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o(n2) time. We show that both problems can be solved in O( n2loglogn/logn) time with O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G. More generally, for any parameter Sâ̂̂[( logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.

AB - Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o(n2) time. We show that both problems can be solved in O( n2loglogn/logn) time with O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G. More generally, for any parameter Sâ̂̂[( logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.

U2 - 10.1016/j.comgeo.2012.01.016

DO - 10.1016/j.comgeo.2012.01.016

M3 - Journal article

SN - 0925-7721

VL - 46

SP - 831

EP - 838

JO - Computational Geometry

JF - Computational Geometry

IS - 7

ER -

Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater