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.