Data structures on event graphs

Bernard Chazelle; Wolfgang Mulzer

doi:10.1007/978-3-642-33090-2_28

Data structures on event graphs

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
Pages	313-324
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-33090-2_28
State	Published - 2012
Externally published	Yes
Event	20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, Slovenia Duration: Sep 10 2012 → Sep 12 2012

Publication series

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

Other

Other	20th Annual European Symposium on Algorithms, ESA 2012
Country/Territory	Slovenia
City	Ljubljana
Period	9/10/12 → 9/12/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

@inproceedings{602525ee8d0c4063bca6210ef5f0d21e,

title = "Data structures on event graphs",

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.",

author = "Bernard Chazelle and Wolfgang Mulzer",

year = "2012",

doi = "10.1007/978-3-642-33090-2_28",

language = "English (US)",

isbn = "9783642330896",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "313--324",

booktitle = "Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings",

note = "20th Annual European Symposium on Algorithms, ESA 2012 ; Conference date: 10-09-2012 Through 12-09-2012",

}

Chazelle, B & Mulzer, W 2012, Data structures on event graphs. in Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7501 LNCS, pp. 313-324, 20th Annual European Symposium on Algorithms, ESA 2012, Ljubljana, Slovenia, 9/10/12. https://doi.org/10.1007/978-3-642-33090-2_28

Data structures on event graphs. / Chazelle, Bernard; Mulzer, Wolfgang.
Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings. 2012. p. 313-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7501 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Data structures on event graphs

AU - Chazelle, Bernard

AU - Mulzer, Wolfgang

PY - 2012

Y1 - 2012

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 -

Data structures on event graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this