Almost Optimal Distance Oracles for Planar Graphs

Prelegent(ci)

Panagiotis Charalampopoulos

Afiliacja

King's College London and University of Warsaw

Termin

9 stycznia 2020 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---