Optimal vertex connectivity oracles
Seth Pettie, Thatchaphol Saranurak, Longhui Yin · 2022
A k-vertex connectivity oracle for undirected G is a data structure that, given u,v∈ V(G), reports min{k,κ(u,v)}, where κ(u,v) is the pairwise vertex connectivity between u,v. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [Inf. Process. Lett. 2012] shows that a data structure of total size O(knlogn), which can even be encoded as a O(klog3 n)-bit labeling scheme, can answer vertex-connectivity queries in O(klogn) time. The construction time is polynomial, but unspecified.