TY - GEN

T1 - Data structures on event graphs

AU - Chazelle, Bernard

AU - Mulzer, Wolfgang

PY - 2012/10/1

Y1 - 2012/10/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84866683857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866683857&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33090-2_28

DO - 10.1007/978-3-642-33090-2_28

M3 - Conference contribution

AN - SCOPUS:84866683857

SN - 9783642330896

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 313

EP - 324

BT - Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings

T2 - 20th Annual European Symposium on Algorithms, ESA 2012

Y2 - 10 September 2012 through 12 September 2012

ER -