External Data Structures for Shortest Path Queries on Planar Digraphs

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationAlgorithms and Computation : 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005. Proceedings
EditorsXiaotie Deng, Dingzhu Du
Number of pages10
PublisherSpringer
Publication year2005
Pages328-338
ISBN (print)978-3-540-30935-2
DOIs
Publication statusPublished - 2005
Event16th Annual International Symposium on Algorithms and Computation - SAAC 2005 - Sanya, Hainan, China
Duration: 19 Dec 200521 Dec 2005
Conference number: 16

Conference

Conference16th Annual International Symposium on Algorithms and Computation - SAAC 2005
Nummer16
LandChina
BySanya, Hainan
Periode19/12/200521/12/2005
SeriesLecture Notes in Computer Science
Volume3827

See relations at Aarhus University Citationformats

ID: 10650457