Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950931 | Information Processing Letters | 2017 | 6 Pages |
Abstract
Within a study of scheduling problems with gaps, Chrobak et al. (CIAC 2015) have shown how to find γ points on the line that hit a maximum number of intervals, in a given family of n intervals, in O(γn2) time. The problem is equivalent to finding γ cliques in an interval graph that cover a maximum number of distinct vertices. We give refined algorithms that run faster if the interval graph of the family is sparse.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter Damaschke,