Standard
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 › fagfællebedømt
Harvard
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
APA
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 (s. 351-362). Association for Computing Machinery.
https://doi.org/10.1137/1.9781611974331.ch26
Vancouver
Wulff-Nilsen C.
Approximate distance oracles for planar graphs with improved query time-space tradeoff. I Krauthgamer R, red., 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Association for Computing Machinery. 2016. s. 351-362
https://doi.org/10.1137/1.9781611974331.ch26
Author
Wulff-Nilsen, Christian. / Approximate distance oracles for planar graphs with improved query time-space tradeoff. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. red. / Robert Krauthgamer. Association for Computing Machinery, 2016. s. 351-362
Bibtex
@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",
}
RIS
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 -
