Data Structures on Event Graphs

Bernard Chazelle, Wolfgang Mulzer

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)1007-1020
Number of pages14
JournalAlgorithmica
Volume71
Issue number4
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Data Structure
  • Low entropy
  • Markov Chain
  • Successor searching

Fingerprint Dive into the research topics of 'Data Structures on Event Graphs'. Together they form a unique fingerprint.

Cite this