AMBIVALENT DATA-STRUCTURES FOR DYNAMIC 2-EDGE-CONNECTIVITY AND K SMALLEST SPANNING-TREES

Ambivalent data structures are presented for several problems on undir ected 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 n umber of vertices in the graph. The techniques are extended to find th e ic smallest spanning trees in an embedded planar graph in O(n + k(lo g n)(3)) time. Ambivalent data structures are also used to dynamically maintain 2-edge-connectivity information. Edges and vertices can be i nserted or deleted in O(m(1/2)) time, and a query as to whether two ve rtices 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.