Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Dynamising Interval Scheduling: The Monotonic Case
verfasst von : Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, Jiamou Liu
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate dynamic algorithms for the interval scheduling problem. We focus on the case when the set of intervals is monotonic. This is when no interval properly contains another interval. We provide two data structures for representing the intervals that allow efficient insertion, removal and various query operations. The first dynamic algorithm, based on the data structure called compatibility forest, runs in amortised time
O
(log
2
n
) for insertion and removal and
O
(log
n
) for query. The second dynamic algorithm, based on the data structure called linearised tree, runs in time
O
(log
n
) for insertion, removal and query. We discuss differences and similarities of these two data structures through theoretical and experimental results.