Worst-Case Union-Find with Fast Deletions

Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

Abstract

In the classical union-find problem we maintain a partition of a universe of elements into disjoint sets subject to the operations union and find. Kaplan et al. [SODA 2002] studied an extension of this problem, where also deletions are allowed. They gave a data structure that for any fixed k supports find(x) and delete(x) in O(logkn) worst-case time and union in O(k) worst-case time, where n is the number of elements in the set containing x. They asked if the delete time could be made faster than their find time. We answer this question affirmatively showing how to get the delete time down to O(logn), while keeping the same time bounds for union and find.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2003-25
Antal sider11
ISBN (Elektronisk)87-7949-034-4
StatusUdgivet - dec. 2003
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2003-25
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Worst-Case Union-Find with Fast Deletions'. Sammen danner de et unikt fingeraftryk.

Citationsformater