Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs

DOI10.1016/j.tcs.2018.08.024zbMath1411.68082OpenAlexW2889518945MaRDI QIDQ1727393

Qian-Ping Gu, Gengchun Xu

Publication date: 20 February 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.08.024

zbMATH Keywords

planar graphsgraph decompositionapproximate algorithmsdistance oracle

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

Shortest-Path Queries in Geometric Networks

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• A fully dynamic approximation scheme for shortest paths in planar graphs
• Surpassing the information theoretic bound with fusion trees
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Robust Distance Queries on Massive Networks
• Fast Algorithms for Finding Nearest Common Ancestors
• Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A Separator Theorem for Planar Graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Improved sparse covers for graphs excluding a fixed minor
• Compact oracles for reachability and approximate distances in planar digraphs
• More Compact Oracles for Approximate Distances in Undirected Planar Graphs

This page was built for publication: Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs