Skip to main content

Data Structures on Event Graphs

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

To refer to this page use:
Abstract: We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by 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 (random or adversarial) 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: 2015
Citation: Chazelle, Bernard, and Wolfgang Mulzer. "Data Structures on Event Graphs." Algorithmica 71, no. 4 (2015): pp. 1007-1020. doi:10.1007/s00453-013-9838-4
DOI: 10.1007/s00453-013-9838-4
ISSN: 0178-4617
EISSN: 1432-0541
Pages: 1007 - 1020
Type of Material: Journal Article
Journal/Proceeding Title: Algorithmica
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.