Union-find with deletions

Haim Kaplan, Nira Shafrir, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A, B,C) replaces sets A and B in the partition by their union, given the name C. The operation find(x) returns the name of the set containing the element x. In this paper we revisit the union-find problem in a context where the underlying partitioned universe is not fixed. Specifically, we allow a delete(x) operation which removes the element x from the set containing it. We consider both worst-case performance and amortized performance. In both settings the challenge is to dynamically keep the size of the structure representing each set proportional to the number of elements in the set which may now decrease as a result of deletions. For any fixed k, we describe a data structure that supports find and delete in O(logfcn) worst-case time and union in 0(k) worst-case time. This matches the best possible worst-case bounds for find and union in the classical setting. Furthermore, using an incremental global rebuilding technique we obtain a reduction converting any union-find data structure to a union-find with deletions data structure. Our reduction is such that the time bounds for find and union change only by a constant factor. The time it takes to delete an element x is the same as the time it takes to find the set containing x plus the time it takes to unite a singleton set with this set. In an amortized setting a classical data structure of Tarjan supports a sequence of m finds and at most n unions on a universe of n elements in 0(n + mα(m + n, n, log n)) time where α(m,n,l) = min{A; |Ak(|m/n|) > 0 and Ai(j) is Ackermann's function as described in [6]. We refine the analysis of this data structure and show that in fact the cost of each find is proportional to the size of the corresponding set. Specifically, we show that one can pay for a sequence of union and find operations by charging a constant to each participating element and 0(α(m,n, log(Z))) for a find of an element in a set of size I. We also show how keep these amortized costs for each find and each participating element while allowing deletions. The amortized cost of deleting an element from a set of I elements is the same as the amortized cost of finding the element; namely, 0(a(m, n, log(i))).

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages19-28
Number of pages10
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period1/6/021/8/02

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Union-find with deletions'. Together they form a unique fingerprint.

  • Cite this

    Kaplan, H., Shafrir, N., & Tarjan, R. E. (2002). Union-find with deletions. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 (pp. 19-28). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002). Association for Computing Machinery.