演讲人： Uri Zwick Tel Aviv University
时间： 2005-09-19 13:30-2005-09-19 13:30
地点：FIT-1-222, Tsinghua University
内容：
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.
个人简介:
