Union-find with constant time deletions
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Union-find with constant time deletions. / Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri.
In: A C M Transactions on Algorithms, Vol. 11, No. 1, 6, 2014.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Union-find with constant time deletions
AU - Alstrup, Stephen
AU - Thorup, Mikkel
AU - Gørtz, Inge Li
AU - Rauhe, Theis
AU - Zwick, Uri
PY - 2014
Y1 - 2014
N2 - A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O(log n) worst-case and O(α⌈ M/N⌉ (n)) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α⌈ M/N⌉(n) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o(log n) worst-case time. 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 worst-case time, while still supporting find operations in O(log n) worst-case time and O(α⌈ M/N⌉ (n)) amortized time.Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O(α⌈ M/N⌉ (n)) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O(α⌈ M/N⌉ (N)). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting.
AB - A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O(log n) worst-case and O(α⌈ M/N⌉ (n)) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α⌈ M/N⌉(n) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o(log n) worst-case time. 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 worst-case time, while still supporting find operations in O(log n) worst-case time and O(α⌈ M/N⌉ (n)) amortized time.Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O(α⌈ M/N⌉ (n)) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O(α⌈ M/N⌉ (N)). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting.
KW - Union-find, disjoint sets
U2 - 10.1145/2636922
DO - 10.1145/2636922
M3 - Journal article
VL - 11
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 1
M1 - 6
ER -
ID: 123163958