SRC Research Report 143

To Provide or To Bound: Sampling in Fully Dynamic Graph Algorithms

Monika R. Henzinger and Mikkel Thorup

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^3n) to O(log^2 n).

Back to the SRC Research Reports main page.

• PostScript compressed with UNIX compress -- 44 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 33 Kbytes
  
• PostScript compressed with ZIP -- 33 Kbytes
  
• PostScript -- 96 Kbytes
  
• Portable Document Format (PDF) -- 112 Kbytes