Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension

DOI10.1145/2818694zbMath1398.68381OpenAlexW2343281498MaRDI QIDQ4962222

Cyril Gavoille, Shiri Chechik, Ittai Abraham, David Peleg

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2818694

zbMATH Keywords

fault-tolerancecompact routingforbidden setsdoubling dimensiondistance labeling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Approximation algorithms (68W25)

Related Items (7)

Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Fault-tolerant distance labeling for planar graphs

This page was built for publication: Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension