Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs

DOI10.1007/978-3-662-48971-0_53zbMath1411.68081arXiv1706.03108OpenAlexW2400880491MaRDI QIDQ3459900

Gengchun Xu, Qian-Ping Gu

Publication date: 11 January 2016

Published in: Algorithms and Computation (Search for Journal in Brave)

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

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 (7)

Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Unnamed Item ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs

This page was built for publication: Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs