An external memory data structure for shortest path queries

DOI10.1016/S0166-218X(02)00217-2zbMath1011.68022OpenAlexW2140883685MaRDI QIDQ1861568

Yanyan Li

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00217-2

zbMATH Keywords

planar graphsshortest pathsgraph algorithmsexternal-memory algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications, Succinct and I/O efficient data structures for traversal in trees, I/O-efficient algorithms for computing planar geometric spanners, An external-memory depth-first search algorithm for general grid graphs, Data structures for categorical path counting queries, Unnamed Item, An external memory data structure for shortest path queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Algorithms for parallel memory, I: Two-level memories
• Algorithms for parallel memory. II: Hierarchical multilevel memories
• Efficient external memory algorithms by simulating coarse-grained parallel algorithms
• An external memory data structure for shortest path queries
• Blocking for external graph searching
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Edge Separators of Planar and Outerplanar Graphs With Applications
• Planar graph decomposition and all pairs shortest paths
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• The buffer tree: A new technique for optimal I/O-algorithms
• Fibonacci heaps and their uses in improved network optimization algorithms
• Faster shortest-path algorithms for planar graphs
• Approximating shortest paths on weighted polyhedral surfaces