Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-062 | 14th December 1995 00:00

On Data Structure Tradeoffs and an Application to Union-Find

RSS-Feed




TR95-062
Authors: Amir M. Ben-Amram, Zvi Galil
Publication: 17th December 1995 10:59
Downloads: 1103
Keywords: 


Abstract:


Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some applications
of this technique.
On the other hand, when a given algorithm achieves similar
amortized performance, we may be able to obtain from it a family
of algorithms that exhibit the underlying tradeoff. We exemplify this by
a family of union-find algorithms trading union time for find time.
The algorithms are obtained in a simple way from the well known path
compression algorithm.


Comment(s):

Comment #1 to TR95-062 | 31st August 1998 15:11

Error Correction Comment on: TR95-062





Comment #1
Authors: Amir M. Ben-Amram
Accepted on: 31st August 1998 15:11
Downloads: 648
Keywords: 


Abstract:

A remark made in the paper regarding the complexity of union-find
is corrected.




ISSN 1433-8092 | Imprint