Refined algorithms for hitting many intervals
详细信息 查看全文
- 作者：Peter Damaschke ; ptr@chalmers.se" class="auth_mail" title="E-mail the corresponding author
- 关键词：Analysis of algorithms ; Scheduling with gaps ; Hitting set ; Interval graph ; Dynamic programming
- 刊名：Information Processing Letters
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：118
- 期：Complete
- 页码：117-122
- 全文大小：273 K
文摘
- •
Partial hitting sets in interval families are of interest for scheduling with gaps.
- •
Optimal partial hitting sets can be computed faster in sparse interval graphs.
- •
Different dynamic programming algorithms are tailored to different input parameters.