MADALGO seminar
MADALGO theory seminar: Tsvi Kopelowitz, University of Michigan
Info about event
Time
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