An External Memory Data Structure for Shortest Path Queries (Extended Abstract) | Zendy

D. A. W. Hutchinson | Zendy; Anil Maheshwari | Zendy; Norbert Zeh | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An External Memory Data Structure for Shortest Path Queries (Extended Abstract)

Author(s) -

D. A. W. Hutchinson,

Anil Maheshwari,

Norbert Zeh

Publication year - 1999

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-66200-6

DOI - 10.1007/3-540-48686-0_5

Subject(s) - shortest path problem , planar graph , computer science , construct (python library) , data structure , path (computing) , planar , graph , theoretical computer science , outerplanar graph , auxiliary memory , distance , pathwidth , line graph , computer network , computer graphics (images) , computer hardware , programming language

We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research