2023/07/14 by Shiri Chechik, Shay Mozes, Chechik, Shiri +3
Computer Science · #Advanced Graph Theory Research #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2307.07222
openalex publication_date 2023/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show how to assign labels of size O(1) to the vertices of a directed planar graph G, such that from the labels of any three vertices s,t,f we can deduce in O(1) time whether t is reachable from s in the graph G∖ \f\. Previously it was only known how to achieve O(1) queries using a centralized O(n) size oracle [SODA'21].