Aarhus University Seal

MADALGO seminar

MADALGO theory seminar: Tsvi Kopelowitz, University of Michigan

Info about event

Time

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

Location: Nygaard 298 NOTICE! DIFFERENT LOCATION!

 

Abstract

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