Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
This paper presents a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time and is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries.
Yao-Wei Long, Seth Pettie, Thatchaphol Saranurak
· 0 citations