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 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.