# Data Structures on Event Graphs

## Author(s): Chazelle, Bernard; Mulzer, Wolfgang

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr16r71
 Abstract: We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by the model of Markov chains. We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete, and query. The algorithm responds to the requests as it encounters them during a (adversarial or random) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal. Publication Date: 2012 Citation: Chazelle, Bernard, and Wolfgang Mulzer. "Data Structures on Event Graphs." European Symposium on Algorithms (2012): pp. 313-324. doi:10.1007/978-3-642-33090-2_28 DOI: 10.1007/978-3-642-33090-2_28 ISSN: 0302-9743 EISSN: 1611-3349 Pages: 313 - 324 Type of Material: Conference Article Journal/Proceeding Title: European Symposium on Algorithms Version: Author's manuscript