We state a new sampling lemma and use it to improvethe running time of dynamic graph algorithms. For thedynamic conectivity problem the previously best randomized algorithm takes expected time O(log sup 3n) per update, amortized over Omiga(m) updates. using the new sampling lemma, we improve its running time to O(log sup 2n). There exists a lower bound in the cell probe model for the time per operation of Omiga(log n/log log n) for this problem. Similarly improved running times are achieveed for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.
展开▼
