Optimal vertex connectivity oracles

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 ( kn log n ), which can even be encoded as a O ( k log 3 n )-bit labeling scheme, can answer vertex-connectivity queries in O ( k log n ) time. The construction time is polynomial, but unspecified.

Authors

• Seth Pettie
• Thatchaphol Saranurak
• Longhui Yin

Keywords

• data structures
• graph connectivity
• space lower bounds