File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches

TitleAnalyzing self-adjusting linear list algorithms with deletions and unsuccessful searches
Authors
Hui, LCKMartel, CU
KeywordsAnalysis Of Algorithm
Competitive Analysis
Data Structures
Self-Adjusting Lists
Issue Date1996
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 1996, v. 58 n. 5, p. 231-236 How to Cite?
DOI: http://dx.doi.org/10.1016/0020-0190(96)00064-6
AbstractIn (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.
Persistent Identifierhttp://hdl.handle.net/10722/152379
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorHui, LCKen_US
dc.contributor.authorMartel, CUen_US
dc.date.accessioned2012-06-26T06:37:47Z-
dc.date.available2012-06-26T06:37:47Z-
dc.date.issued1996en_US
dc.identifier.citationInformation Processing Letters, 1996, v. 58 n. 5, p. 231-236en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/10722/152379-
dc.description.abstractIn (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.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_US
dc.relation.ispartofInformation Processing Lettersen_US
dc.subjectAnalysis Of Algorithmen_US
dc.subjectCompetitive Analysisen_US
dc.subjectData Structuresen_US
dc.subjectSelf-Adjusting Listsen_US
dc.titleAnalyzing self-adjusting linear list algorithms with deletions and unsuccessful searchesen_US
dc.typeArticleen_US
dc.identifier.emailHui, LCK:hui@cs.hku.hken_US
dc.identifier.authorityHui, LCK=rp00120en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/0020-0190(96)00064-6en_US
dc.identifier.scopuseid_2-s2.0-3743070665en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-3743070665&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume58en_US
dc.identifier.issue5en_US
dc.identifier.spage231en_US
dc.identifier.epage236en_US
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridHui, LCK=8905728300en_US
dc.identifier.scopusauthoridMartel, CU=35589077100en_US
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats