Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs

2017/07/08 by Itay Laish, Shay Mozes, Laish, Itay +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1707.02414

openalex publication_date 2017/07/08 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

Let G be a graph where each vertex is associated with a label. A Vertex-Labeled Approximate Distance Oracle is a data structure that, given a vertex v and a label λ, returns a (1+ε)-approximation of the distance from v to the closest vertex with label λ in G. Such an oracle is dynamic if it also supports label changes. In this paper we present three different dynamic approximate vertex-labeled distance oracles for planar graphs, all with polylogarithmic query and update times, and nearly linear space requirements.

Related

• Efficient Vertex-Label Distance Oracles for Planar Graphs
• Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
• (1+epsilon)-Distance Oracle for Planar Labeled Graph
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs