Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. - Holm, Jacob
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for connectivity, O(log4 n) for minimum spanning forest, 2-edge connectivity, and O(log5 n) biconnectivity.
Keywords: Data; Data structures; Theory of computation; Analysis of algorithms and problem complexity; Nonnumerical algorithms and problems; Computations on discrete structures; Mathematics of computing; Discrete mathematics; Graph theory; Graph algorithms; Algorithms