An efficient data structure for the simulation event set

Abstract

Recently algorithms have been presented for the realization of event scheduling routines suitable for general purpose discrete event simulation systems. Several exhibited a performance superior to that of commonly used simple linked list algorithms. In this paper a new event scheduling algorithm is presented which improves on two aspects of the best of the previously published algorithms. First, the new algorithm's performance is quite insensitive to skewed distributions, and second, its worst-case complexity is O(√n), where n is the number of events in the set. Furthermore, tests conducted to estimate the average complexity showed it to be nearly independent of n.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 57 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.