Data structures on event graphs

Bernard Chazelle, Wolfgang Mulzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
Pages313-324
Number of pages12
DOIs
StatePublished - Oct 1 2012
Event20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, Slovenia
Duration: Sep 10 2012Sep 12 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7501 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th Annual European Symposium on Algorithms, ESA 2012
CountrySlovenia
CityLjubljana
Period9/10/129/12/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Data structures on event graphs'. Together they form a unique fingerprint.

Cite this