In this paper we present space-query trade-offs for external memory data structures that answer shortest path queries on planar directed graphs. For any S = Ω(N 1 + ε) and S = O(N2/B), our main result is a family of structures that use S space and answer queries in O(N2/ S B) I/Os, thus obtaining optimal space-query product O(N2/B). An S space structure can be constructed in O(√S · sort(N)) I/Os, where sort(N) is the number of I/Os needed to sort N elements, B is the disk block size, and N is the size of the graph.
Algorithms and Computation: 16th International Symposium, Isaac 2005, Sanya, Hainan, China, December 19-21, 2005. Proceedings, 2005, p. 328-338
Lecture Notes in Computer Science
16th Annual International Symposium on Algorithms and Computation - SAAC 2005