Speaker: Uri Zwick Tel Aviv University
Time: 2005-09-19 13:30-2005-09-19 14:30
Venue: FIT-1-222

Abstract:

A union-find data structure maintains a collection of disjoint sets under MAKESET, UNION and FIND operations. Kaplan, Shafrir and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which elements of the sets maintained may be deleted. The cost of a DELETE operation in their implementations is the same as the cost of a FIND operation. They left open the question whether DELETE operations can be implemented more efficiently than FIND operations. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports DELETE, as well as MAKESET and UNION, operations in *constant* time, while still supporting FIND operations in O(log n) worst-case time and O(alpha(n)) amortized time, where n is the number of elements in the set returned by the FIND operation, and alpha(n) is a functional inverse of Ackermann's function.
Joint work with Stephen Alstrup, Inge Li Goertz, Theis Rauhe and Mikkel Thorup.
 

Short Bio: