Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
Greg N. Frederickson · SIAM Journal on Computing · 1997
Ambivalent data structures are presented for several problems on undirected graphs. These data structures are used in finding the k smallest spanning trees of a weighted undirected graph in $O(m \log \beta (m,n) + \min \{ k^{3/2}, km^{1/2} \} )$ time, where m is the number of edges and n the number of vertices in the graph. The techniques are extended to find the k smallest spanning trees in an embedded planar graph in $O(n + k (\log n)^3 )$ time. Ambivalent data structures are also used to dynamically maintain 2-edge-connectivity information. Edges and vertices can be inserted or deleted in $O(m^{1/2})$ time, and a query as to whether two vertices are in the same 2-edge-connected component can be answered in $O(\log n)$ time, where m and n are understood to be the current number of edges and vertices, respectively.