Dynamic algorithms for monotonic interval scheduling problem

DOI10.1016/j.tcs.2014.09.046zbMath1303.68167arXiv1412.8005OpenAlexW1417332038MaRDI QIDQ476865

Bakhadyr Khoussainov, Mikhail Kokho, Jiamou Liu, Aleksandr Nikolaevich Gavryushkin

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.8005

zbMATH Keywords

data structuresdynamic algorithmsinterval scheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Data structures (68P05)

Related Items

Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ The hull number in the convexity of induced paths of order \(3\)

Cites Work

• Unnamed Item
• Unnamed Item
• Maintenance of a piercing set for intervals with applications
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A data structure for dynamic trees
• A new representation of proper interval graphs with an application to clique-width
• Dynamising Interval Scheduling: The Monotonic Case
• Interval scheduling: A survey
• Dynamic rectangular intersection with priorities
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Self-adjusting binary search trees
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs

This page was built for publication: Dynamic algorithms for monotonic interval scheduling problem