Reactive proximity data structures for graphs

DOI10.1007/978-3-319-77404-6_56MaRDI QIDQ2294736zbMATH OpenOpenAlexFDO

Authors David Eppstein, Michael T. Goodrich, Nil Mamano

Publication date 12 February 2020

Full work available at URL https://arxiv.org/abs/1803.04555

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider data structures for graphs where we maintain a subset of the nodes called sites, and allow proximity queries, such as asking for the closest site to a query node, and update operations that enable or disable nodes as sites. We refer to a data structure that can efficiently react to such updates as reactive. We present novel reactive proximity data structures for graphs of polynomial expansion, i.e., the class of graphs with small separators, such as planar graphs and road networks. Our data structures can be used in several logistical problems and geographic information systems dealing with real-time data, such as emergency dispatching. We experimentally compare our data structure to Dijkstra's algorithm in a system emulating random queries in a real road network.

Recommendations

• scientific article; zbMATH DE number 3900809
• scientific article; zbMATH DE number 6469222
• Improved distance queries in planar graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Oracles for bounded-length shortest paths in planar graphs

This page was built for publication: Reactive proximity data structures for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294736)