Maintaining order in a list

Karim Douieb

In this talk, I will present a simple algorithm for maintaining a total order subject to insertions, deletions and precedence queries (determine whether an element precedes another in the total order). This work was introduced by Bender, Cole, Demaine, Farach-Colton and Zito as a simplification of the optimal solutions of Dietz and Sleator.