Dynamic algorithms for monotonic interval scheduling problem

作     者：Gavruskin, Alexander Khoussainov, Bakhadyr Kokho, Mikhail Liu, Jiamou 

作者机构：Univ Auckland Dept Comp Sci Auckland 1 New Zealand Auckland Univ Technol Sch Comp & Math Sci Auckland New Zealand 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2015年第562卷第C期

页      面：227-242页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Marsden Fund of the Royal Society of New Zealand [10-UOA-165] 

主　　题：Interval scheduling Dynamic algorithms Data structures 

摘      要：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 (logn) for query. The second dynamic algorithm, based on the data structure called linearised tree, runs in time O (logn) for insertion, removal and query. We discuss differences and similarities of these two data structures through theoretical and experimental results. (C) 2014 Elsevier B.V. All rights reserved.