Please use this identifier to cite or link to this item:
https://doi.org/10.1016/0020-0190(96)00064-6
Title: | Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches | Authors: | Hui, L.C.K. Martel, C.U. |
Keywords: | Analysis of algorithm Competitive analysis Data structures Self-adjusting lists |
Issue Date: | 10-Jun-1996 | Citation: | Hui, L.C.K.,Martel, C.U. (1996-06-10). Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches. Information Processing Letters 58 (5) : 231-236. ScholarBank@NUS Repository. https://doi.org/10.1016/0020-0190(96)00064-6 | Abstract: | In (Hui and Martel, 1993), we designed and analyzed efficient self-adjusting linear list algorithms. Our analysis proves that a self-adjusting linear list algorithm, MP, is competitive to a large class of offline adversaries, where the operations are successful searches, unsuccessful searches, and insertions. Analysis of deletions is listed as an open question. This paper presents an improved version of MP which is also able to handle deletions efficiently, and proves that the new MP algorithm is 6-competitive to offline adversaries when considering successful searches, unsuccessful searches, insertions, and deletions. | Source Title: | Information Processing Letters | URI: | http://scholarbank.nus.edu.sg/handle/10635/99191 | ISSN: | 00200190 | DOI: | 10.1016/0020-0190(96)00064-6 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.