| Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms (1997) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 dyamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log 3 n) to O(log 2 n). 1 Introduction In this paper we present a new sampling lemma, and use it to improve the running times of various fully dynamic graph algorithms. We consider the following provide-or-bound problem: Let S be a set with a subset R ` S. Given (1) an oracle to uniformly sample elements in S, (2) an oracle to test membership in R, and (3) the parameters s = jSj and ` ? 1 either (i) provide an element of R, o... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||