Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
, , and .
J. ACM 48 (4): 723--760 (July 2001)

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 <i>n</i> vertices, the amortized operation costs are <i>O</i>(log<sup>2</sup> <i>n</i>) for connectivity, <i>O</i>(log<sup>4</sup> <i>n</i>) for minimum spanning forest, 2-edge connectivity, and <i>O</i>(log<sup>5</sup> <i>n</i>) biconnectivity.
  • @mhwombat
  • @dblp
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).