Abstract
For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: For any S ϵ n 3/2, we show how to obtain an S-space distance 5/2 oracle that answers queries in time O(S n 3/2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1/4) query time.
| Original language | English |
|---|---|
| Title of host publication | 2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS) |
| Publisher | IEEE |
| Publication date | 10 Nov 2017 |
| Pages | 962-973 |
| DOIs | |
| Publication status | Published - 10 Nov 2017 |
| Event | 58th Annual IEEE Symposium on Foundations of Computer Science - Berkeley, United States Duration: 15 Oct 2017 → 17 Oct 2017 Conference number: 58 |
Conference
| Conference | 58th Annual IEEE Symposium on Foundations of Computer Science |
|---|---|
| Number | 58 |
| Country/Territory | United States |
| City | Berkeley |
| Period | 15/10/2017 → 17/10/2017 |
Keywords
- dynamic graph algorithms
- minimum spanning forests
- graph decomposition