Sampling to provide or to bound: With applications to fully dynamic graph algorithms

In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a (small) upper bound on the size of R that holds with high probability. We give an optimal algorithm for this problem. This algorithm improves the time per operation for various dynamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log3n) to O(log2n).

Published in:
Random Struct. Algorithms, 11, 4, 369-379
Other identifiers:
Scopus: 2-s2.0-0040058197

 Record created 2007-01-18, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)