Confluently persistent deques via data structural bootstrapping

Adam L. Buchsbaum, Robert E. Tarjan

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

Abstract

We introduce data structural bootstrapping, a technique to design data structures recursively, and use it to design confluently persistent deques. Our data structure requires O(log*k) amortized time and space per deletion, where k is the total number of deque operations, and constant amortized time for other operations. This improves a previous result of Driscoll, Sleator, and Tarjan.

Original languageEnglish (US)
Pages155-164
Number of pages10
StatePublished - Jan 1 1993
Externally publishedYes
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Confluently persistent deques via data structural bootstrapping'. Together they form a unique fingerprint.

Cite this