Dynamising Interval Scheduling: The Monotonic Case

About this item

Title

Dynamising Interval Scheduling: The Monotonic Case

Content partner

University of Otago

Collection

Otago University Research Archive

Description

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(log2n) for insertion and removal and O(logn) for query. The s...

Read more

Format

Research paper

Research format

Scholarly text / Book item

Thesis level

Book Section

Date created

2013

Creator

Gavruskin, Alexander / Khoussainov, Bakhadyr / Kokho, Mikhail / Liu, Jiamou

URL

https://hdl.handle.net/10523/39548

Related subjects

Binary Search Tree / Dynamic Algorithm / Dynamic Tree / Interval Graph / Interval Schedule

What is the copyright status of this item?

All Rights Reserved

This item is all rights reserved, which means you'll have to get permission from University of Otago before using it.

What can I do with this item?

You must always check with University of Otago to confirm the specific terms of use, but this is our understanding:

Non-infringing use

NZ Copyright law does not prevent every use of a copyright work. You should consider what you can and cannot do with a copyright work.

No sharing

You may not copy and/or share this item with others without further permission. This includes posting it on your blog, using it in a presentation, or any other public use.

No modifying

You are not allowed to adapt or remix this item into any other works.

No commercial use

You may not use this item commercially.