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.

SCOPUSTM   
Citations

1
checked on Oct 14, 2018

Page view(s)

31
checked on Oct 12, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.