Fault-tolerant distance labeling for planar graphs
From MaRDI portal
Publication:5970814
DOI10.1016/j.tcs.2022.03.020MaRDI QIDQ5970814
Panagiotis Charalampopoulos, Aviv Bar-Natan, Shay Mozes, Oren Weimann, Paweł Gawrychowski
Publication date: 10 May 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.03.020
planar graphs; counting shortest paths; fault-tolerant distance labels; forbidden-set distance labels
68Qxx: Theory of computing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact labelings for efficient first-order model-checking
- Better distance labeling for unweighted planar graphs
- Subjective-cost policy routing
- Constrained-path labellings on graphs of bounded clique-width
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Informative labeling schemes for graphs
- Multiple-Source Shortest Paths in Embedded Graphs
- Shortest paths in directed planar graphs with negative lengths
- Labeling schemes for vertex connectivity
- A near-linear-time algorithm for computing replacement paths in planar directed graphs
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- An Optimal Labeling for Node Connectivity
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Implicat Representation of Graphs
- Optimal induced universal graphs for bounded-degree graphs
- Near Optimal Adjacency Labeling Schemes for Power-Law Graphs
- Adjacency Labeling Schemes and Induced-Universal Graphs
- Optimal Induced Universal Graphs and Adjacency Labeling for Trees
- Labeling Schemes for Flow and Connectivity
- Distance labeling in graphs
- Proximity-preserving labeling schemes
- Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
- Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
- Object location using path separators
- Almost optimal distance oracles for planar graphs
- Exact Distance Oracles for Planar Graphs with Failing Vertices
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Improved algorithms for min cut and max flow in undirected planar graphs
- Compact oracles for reachability and approximate distances in planar digraphs
- Structured recursive separator decompositions for planar graphs in linear time
- Short Labels by Traversal and Jumping
