Almost Optimal Distance Oracles for Planar Graphs

Speaker(s)

Panagiotis Charalampopoulos

Affiliation

King's College London and University of Warsaw

Date

Jan. 9, 2020, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the naive linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space O(n^1+ε) and query-time Õ(1) for any constant ε>0, (ii) an oracle with space Õ(n) and query-time Ο(n^ε) for any constant ε >0, and (iii) an oracle with space n^1+ο(1) and query-time n^ο(1).

Joint work with P. Gawrychowski, S. Mozes and O. Weimann.

---