# Improved Sampling with Applications to Dynamic Graph Algorithms

## No Access Until

##### Permanent Link(s)

## Collections

## Other Titles

## Author(s)

## Abstract

We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time