Loading...
research article
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).
Type
research article
Scopus ID
2-s2.0-0040058197
Authors
Publication date
1997
Published in
Volume
11
Issue
4
Start page
369
End page
379
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 18, 2007
Use this identifier to reference this record