Access Restriction

Author Franta, W. R. ♦ Maly, Kurt
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Time flow mechanisms ♦ Event scanning mechanisms ♦ Simulation ♦ Multilinked lists
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.
Description Affiliation: Univ. of Minnesota, Minneapolis (Franta, W. R.; Maly, Kurt)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 8
Page Count 7
Starting Page 596
Ending Page 602

Open content in new tab

   Open content in new tab
Source: ACM Digital Library