Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queues

Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan

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

6 Scopus citations

Abstract

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages40-49
Number of pages10
ISBN (Electronic)0818629002
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
CountryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queues'. Together they form a unique fingerprint.

  • Cite this

    Buchsbaum, A. L., Sundar, R., & Tarjan, R. E. (1992). Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queues. In Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 (pp. 40-49). [267820] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267820