Mr. Henzinger et M. Thorup, SAMPLING TO PROVIDE OR TO BOUND - WITH APPLICATIONS TO FULLY DYNAMIC GRAPH ALGORITHMS, Random structures & algorithms, 11(4), 1997, pp. 369-379
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 o
f generating random elements from S testing for membership in R, eithe
r (i) provide an element of R, or (ii) give a (small) upper bound on t
he size of R that holds with high probability. We give an optimal algo
rithm for this problem. This algorithm improves the time per operation
for various dynamic graph algorithms by a factor of O(log n). For exa
mple, it improves the time per update for fully dynamic connectivity f
rom O(log(3)n) to O(log(2)n). (C) 1997 John Wiley & Sons, Inc.