ECCC-Report TR95-062https://eccc.weizmann.ac.il/report/1995/062Comments and Revisions published for TR95-062en-usMon, 31 Aug 1998 15:11:21 +0300
Comment 1
| Error Correction Comment on: TR95-062 |
Amir M. Ben-Amram
https://eccc.weizmann.ac.il/report/1995/062#comment1A remark made in the paper regarding the complexity of union-find
is corrected.
Mon, 31 Aug 1998 15:11:21 +0300https://eccc.weizmann.ac.il/report/1995/062#comment1
Paper TR95-062
| On Data Structure Tradeoffs and an Application to Union-Find |
Amir M. Ben-Amram,
Zvi Galil
https://eccc.weizmann.ac.il/report/1995/062
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.
Sun, 17 Dec 1995 10:59:11 +0200https://eccc.weizmann.ac.il/report/1995/062