Fault-tolerant distance labeling for planar graphs
From MaRDI portal
Publication:5918639
DOI10.1007/978-3-030-79527-6_18MaRDI QIDQ5918639
Panagiotis Charalampopoulos, Oren Weimann, Paweł Gawrychowski, Aviv Bar-Natan, Shay Mozes
Publication date: 22 March 2022
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.07154
planar graphs; counting shortest paths; fault-tolerant distance labels; forbidden-set distance labels
68R10: Graph theory (including graph drawing) in computer science
68Mxx: Computer system organization
68Q11: Communication complexity, information complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact labelings for efficient first-order model-checking
- Subjective-cost policy routing
- Sublinear-space distance labeling using hubs
- 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
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Compact Forbidden-Set Routing
- 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
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- 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
