## An efficient solution to the order maintenance problem

Institute of Cybernetics at TUT

Thursday, December 2014, 14:00

Cybernetica Bldg (Akadeemia tee 21), room B101

**Abstract**: In the order-maintenance problem, the objective is
to maintain a total order subject to insertions, deletions and
comparisons of elements. In this talk, I will present a solution to
the order-maintenance problem that combines an algorithm by Bender et
al. (2002) with an idea presented by Dietz and Sleator (1987).

A. Bender, R. Cole, E. D. Demaine, M. Farach-Colton, J. Zito. Two
simplified algorithms for maintaining order in a list. In R. Möhring,
R. Raman, eds., *Proc. of ESA 2002*, v. 2461 of *Lect. Notes in
Comput. Sci.*, pp. 152-164. Springer, 2002.

P. F. Dietz, D. D. Sleator. Two algorithms for maintaining order in
a list. In *Proc. of 19th Ann. ACM Symp. on Theory of Computing,
STOC '87*, pp. 365-372. ACM, 1987.

Tarmo Uustalu

Last update 2 December 2014