DocumentCode :
3256488
Title :
Move-to-end is best for double-linked lists
Author :
Estivill-Castro, Vladimir
Author_Institution :
LANIA, Veracruz, Mexico
fYear :
1992
fDate :
28-30 May 1992
Firstpage :
84
Lastpage :
87
Abstract :
The authors demonstrate that Move-to-End (ME) is statically competitive for doubly linked lists. That is, ME is competitive with respect to the class of off-line static heuristics for doubly-linked lists. ME is competitive with respect to the class of on-line dynamic heuristics that use, per query, one end of the doubly-linked list. Moreover, other heuristics, like Swap do not have these properties. Since one can prove that there is no competitive heuristic for the class of on-line dynamic memoryless deterministic heuristics, ME offers the best competitiveness behavior
Keywords :
abstract data types; search problems; Move-to-End heuristic; abstract data type; double-linked lists; off-line static heuristics; on-line dynamic heuristics; self-organizing heursitics; Cost function; Data structures; Dictionaries; Frequency; Organizing; Performance analysis; Tree data structures;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-8186-2812-X
Type :
conf
DOI :
10.1109/ICCI.1992.227699
Filename :
227699
Link To Document :
بازگشت