Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
Yaowei Long, Seth Pettie, Thatchaphol Saranurak · Society for Industrial and Applied Mathematics eBooks · 2025
We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query 〈s, t, F 〉 with |F | ≤ f, we can determine whether s and t are still connected in G — F, given only the labels of F ∪ {s, t }.