P. Dietz
ABSTRACT
The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.
- 1.Baker, H. G. Jr. List Processing in Ileal Time on a Serial Computer. C.ACM 21(4), April 1978, pages 280-294. Google Scholar
Digital Library
- 2.Dietz, P. F. Maintaining Order in a Linked List. Proc. 14th ACM STOC, May 1982, pages t22-127. Google ScholarDigital Library
- 3.Driscoll, J. R., Sarnak, N., Sleator, D. D., Tarjan, R. E. Making Data Structures Persistent. Proc. l$th A CM STOC, May 1986. To appear in JCSS. Google ScholarDigital Library
- 4.Sleator, D. D., Tarjan, R., E. Arn.ortized Efficiency of List Update and Paging Rules. C. A CM 28(2}, February 1985, pages 202-206. Google ScholarDigital Library
- 5.Tarjan, R. E. Amortized Compu'Lational Complexity. SIAM J. AIg. Disc. Meth. 2(6), April 1985, pages 306- 318.Google ScholarCross Ref
- 6.Tsakalidis, A. K. Maintaining Order in a Generalized Linked List. Acts lnformatica, 21(1), 198,i, pages 101- 112. Google ScholarDigital Library
- 7.Wegbreit, B. Retrieval from Context Trees. {afo. Proc. Lett. 3(4), March 1975, pages 119-120.Google ScholarCross Ref
- 8.Willard, D. E. Maintaining Dense :Sequential Files in a Dynamic Environment. Proc. 14th A CM S'TOC, May 1982, pages 114-12/. Google ScholarDigital Library
- 9.Willard, D. E. Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files. A CM SIGMOD 8'6, May 1986, pages 251-260. Google ScholarDigital Library
Index Terms
- Two algorithms for maintaining order in a list
Recommendations
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
We present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to Feigenbaum et al.). Specifically, the processing time per edge of our algorithm ...
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and ProgrammingWe present a streaming algorithm for constructing sparse spanners and show that our algorithm out-performs significantly the state-of-the-art algorithm for this task [20]. Specifically, the processing time-per-edge of our algorithm is drastically ...
List Update Algorithms for Data Compression
DCC '08: Proceedings of the Data Compression ConferenceList update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. The Burrows-Wheeler transform (BWT), which is the basis of many state-of-the-art general purpose compressors applies ...
Comments