Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Authors:
- Shiri ChechikSCShiri Chechik
Preprint
Abstract
We present a labeling scheme that assigns labels of size $\tilde O(1)$ to the vertices of a directed weighted planar graph $G$, such that for any fixed $\varepsilon>0$ from the labels of any three vertices $s$, $t$ and $f$ one can determine in $\tilde O(1)$ time a $(1+\varepsilon)$-approximation of the $s$-to-$t$ distance in the graph $G\setminus\{f\}$. For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting. Even for the easier case of reachability, $\tilde O(1)$ queries were known only with a centralized oracle of size $\tilde O(n)$ [SODA 21].
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Better Distance Labeling for Unweighted Planar GraphsAlgorithmica, 2023
- Single source distance oracle for planar digraphs avoiding a failed node or link2012
- Many Distances in Planar GraphsAlgorithmica, 2010
- Compact labelings for efficient first-order model-checkingJournal of Combinatorial Optimization, 2009
- Constrained-Path Labellings on Graphs of Bounded Clique-WidthTheory of Computing Systems, 2009
- An Optimal Labeling for Node Connectivity2009
- Compact Forbidden-Set Routing2007
- Informative labeling schemes for graphsTheoretical Computer Science, 2005
- Planar spanners and approximate shortest path queries among obstacles in the plane1996
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979