Aarhus University Seal

MADALGO seminar

MADALGO theory seminar: Tsvi Kopelowitz, University of Michigan

Info about event


Wednesday 31 December 1969, at 22:00 - at

Theory Seminar


Order/File-maintenance revisited again


Tsvi Kopelowitz, University of Michigan


Time: Wednesday, June 11 at 14:15 to 15:00




The order-maintenance data structure  is one of the most used black-boxes for many dynamic problems. The data structure allows to maintain a dynamic ordered list in constant time per update (assuming a pointer is given to the location) while supporting constant time order queries in which one wishes to determine the order of two elements in the list. All of these time bounds are in a worst case sense. Unfortunately , the correctness of the known solutions is considered by many to be questionable, due to a black-box usage of another unclear/complex data structure for another problem known as the file-maintenance problem.

We will survey the interesting history of the order maintenance problem and describe a new simple solution that has some additional properties which are useful for applications such as online suffix tree construction and fully persistent arrays. Finally, if time permits we will discuss a new understandable  solution for the file-maintenance problem.

Host: Gerth Stølting Brodal