OFF-LINE ALGORITHMS FOR THE LIST UPDATE PROBLEM

Authors
REINGOLD N WESTBROOK J
Citation
N. Reingold et J. Westbrook, OFF-LINE ALGORITHMS FOR THE LIST UPDATE PROBLEM, Information processing letters, 60(2), 1996, pp. 75-80
Citations number
17
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
2
Year of publication
1996
Pages
75 - 80
Database
ISI
SICI code
0020-0190(1996)60:2<75:OAFTLU>2.0.ZU;2-S
Abstract
Optimum off-line algorithms for the list update problem are investigat ed, The list update problem involves implementing a dictionary of item s as a linear list. Several characterizations of optimum algorithms ar e given; these lead to optimum algorithm which runs in time Theta 2(n) (n - 1)!m, where n is the length of the list and m is the number of re quests. The previous best algorithm, an adaptation of a more general a lgorithm due to Manasse et al. (1988), runs in time Theta(n!)(2)m.