Approximate distance oracles for planar graphs with improved query time-space tradeoff

Christian Wulff-Nilsen

doi:10.1137/1.9781611974331.ch26

Approximate distance oracles for planar graphs with improved query time-space tradeoff

Christian Wulff-Nilsen^*

^*Corresponding author af dette arbejde

Datalogisk Institut

10 Citationer (Scopus)

Abstract

We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed ϵ > 0, we present a (1 + ϵ)-approximate distance oracle with O(n(log log n)²) space and O((loglogr?,)³) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(nlogn) to O(n(loglogn)⁵).

Originalsprog	Engelsk
Titel	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Redaktører	Robert Krauthgamer
Antal sider	12
Forlag	Association for Computing Machinery
Publikationsdato	2016
Sider	351-362
ISBN (Elektronisk)	978-1-61197-433-1
DOI	https://doi.org/10.1137/1.9781611974331.ch26
Status	Udgivet - 2016
Begivenhed	27th Annual ACM-SIAM Symposium on Discrete Algorithms - Arlington, USA Varighed: 10 jan. 2016 → 12 jan. 2016

Konference

Konference	27th Annual ACM-SIAM Symposium on Discrete Algorithms
Land/Område	USA
By	Arlington
Periode	10/01/2016 → 12/01/2016

Adgang til dokumentet

10.1137/1.9781611974331.ch26

1.9781611974331.ch26Forlagets udgivne version, 204 KB

Citationsformater

Approximate distance oracles for planar graphs with improved query time-space tradeoff. / Wulff-Nilsen, Christian.

27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. red. / Robert Krauthgamer. Association for Computing Machinery, 2016. s. 351-362.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Wulff-Nilsen, C 2016, Approximate distance oracles for planar graphs with improved query time-space tradeoff. i R Krauthgamer (red.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Association for Computing Machinery, s. 351-362, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, USA, 10/01/2016. https://doi.org/10.1137/1.9781611974331.ch26

@inproceedings{8836e0e3013d4ceca8b0252701e56214,

title = "Approximate distance oracles for planar graphs with improved query time-space tradeoff",

abstract = "We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed ϵ > 0, we present a (1 + ϵ)-approximate distance oracle with O(n(log log n)2) space and O((loglogr?,)3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(nlogn) to O(n(loglogn)5).",

author = "Christian Wulff-Nilsen",

year = "2016",

doi = "10.1137/1.9781611974331.ch26",

language = "English",

pages = "351--362",

editor = "Robert Krauthgamer",

booktitle = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016",

publisher = "Association for Computing Machinery",

note = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 ; Conference date: 10-01-2016 Through 12-01-2016",

}

TY - GEN

T1 - Approximate distance oracles for planar graphs with improved query time-space tradeoff

AU - Wulff-Nilsen, Christian

PY - 2016

Y1 - 2016

N2 - We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed ϵ > 0, we present a (1 + ϵ)-approximate distance oracle with O(n(log log n)2) space and O((loglogr?,)3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(nlogn) to O(n(loglogn)5).

AB - We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed ϵ > 0, we present a (1 + ϵ)-approximate distance oracle with O(n(log log n)2) space and O((loglogr?,)3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(nlogn) to O(n(loglogn)5).

U2 - 10.1137/1.9781611974331.ch26

DO - 10.1137/1.9781611974331.ch26

M3 - Article in proceedings

AN - SCOPUS:84962808647

SP - 351

EP - 362

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 10 January 2016 through 12 January 2016

ER -

Approximate distance oracles for planar graphs with improved query time-space tradeoff

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater