Better tradeoffs for exact distance oracles in planar graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Standard

Better tradeoffs for exact distance oracles in planar graphs. / Gawrychowski, Pawel; Mozes, Shay; Weimann, Oren; Wulff-Nilsen, Christian.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . red. / A. Czumaj. Society for Industrial and Applied Mathematics, 2018. s. 515-529.

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Gawrychowski, P, Mozes, S, Weimann, O & Wulff-Nilsen, C 2018, Better tradeoffs for exact distance oracles in planar graphs. i A Czumaj (red.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics, s. 515-529, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, USA, 07/01/2018. https://doi.org/10.1137/1.9781611975031.34

APA

Gawrychowski, P., Mozes, S., Weimann, O., & Wulff-Nilsen, C. (2018). Better tradeoffs for exact distance oracles in planar graphs. I A. Czumaj (red.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (s. 515-529). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.34

Vancouver

Gawrychowski P, Mozes S, Weimann O, Wulff-Nilsen C. Better tradeoffs for exact distance oracles in planar graphs. I Czumaj A, red., Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics. 2018. s. 515-529 https://doi.org/10.1137/1.9781611975031.34

Author

Gawrychowski, Pawel ; Mozes, Shay ; Weimann, Oren ; Wulff-Nilsen, Christian. / Better tradeoffs for exact distance oracles in planar graphs. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . red. / A. Czumaj. Society for Industrial and Applied Mathematics, 2018. s. 515-529

Bibtex

@inproceedings{3a1cac827ba44c0ebd350fc1425f3b95,
title = "Better tradeoffs for exact distance oracles in planar graphs",
abstract = "We present an O(n1:5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5=3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S 2 [n; n2], we show an oracle of size S that answers queries in ~O (maxf1; n1:5=Sg) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S 2 [n; n5=3].",
author = "Pawel Gawrychowski and Shay Mozes and Oren Weimann and Christian Wulff-Nilsen",
year = "2018",
doi = "10.1137/1.9781611975031.34",
language = "English",
pages = "515--529",
editor = "A. Czumaj",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Society for Industrial and Applied Mathematics",
address = "United States",
note = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 ; Conference date: 07-01-2018 Through 10-01-2018",

}

RIS

TY - GEN

T1 - Better tradeoffs for exact distance oracles in planar graphs

AU - Gawrychowski, Pawel

AU - Mozes, Shay

AU - Weimann, Oren

AU - Wulff-Nilsen, Christian

PY - 2018

Y1 - 2018

N2 - We present an O(n1:5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5=3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S 2 [n; n2], we show an oracle of size S that answers queries in ~O (maxf1; n1:5=Sg) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S 2 [n; n5=3].

AB - We present an O(n1:5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5=3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S 2 [n; n2], we show an oracle of size S that answers queries in ~O (maxf1; n1:5=Sg) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S 2 [n; n5=3].

UR - http://www.scopus.com/inward/record.url?scp=85045541984&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.34

DO - 10.1137/1.9781611975031.34

M3 - Article in proceedings

AN - SCOPUS:85045541984

SP - 515

EP - 529

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, A.

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -

ID: 204040383