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

DOI10.1007/978-3-662-48971-0_53MaRDI QIDQ3459900zbMATH OpenOpenAlexFDO

Authors Qian-Ping Gu, Gengchun Xu

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

approximate algorithmsdistance oraclegraph decompositionplanar graphs

Mathematics Subject Classification ID

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

Abstract: We give a $(1+epsilon)$-approximate distance oracle with $O(1)$ query time for an undirected planar graph $G$ with $n$ vertices and non-negative edge lengths. For $epsilon>0$ and any two vertices $u$ and $v$ in $G$, our oracle gives a distance $ilded(u,v)$ with stretch $(1+epsilon)$ in $O(1)$ time. The oracle has size $O(nlogn((logn)/epsilon+f(epsilon)))$ and pre-processing time $O(nlogn((lo{g}^{3}n)/epsilo{n}^2+f(epsilon)))$, where $f(epsilon)=2^{O(1/epsilon)}$. This is the first $(1+epsilon)$-approximate distance oracle with $O(1)$ query time independent of $epsilon$ and the size and pre-processing time nearly linear in $n$, and improves the query time $O(1/epsilon)$ of previous $(1+epsilon)$-approximate distance oracle with size nearly linear in $n$.

Recommendations

• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Approximate distance oracles for planar graphs with improved query time-space tradeoff
• More compact oracles for approximate distances in undirected planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Exact distance oracles for planar graphs

Cited in

(15)

• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Faster approximate diameter and distance oracles in planar graphs
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
• Approximate distance oracles for planar graphs with improved query time-space tradeoff
• Better tradeoffs for exact distance oracles in planar graphs
• Approximate distance oracles for geometric spanners
• Near-optimal distance emulator for planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Compact oracles for reachability and approximate distances in planar digraphs
• More compact oracles for approximate distances in undirected planar graphs
• Exact distance oracles for planar graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.

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

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