1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
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
Main Research Area:
Lecture Notes in Computer Science
16th Annual International Symposium on Algorithms and Computation - SAAC 2005