Dan Bergren

dblp:259/4951 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
1since 2021 · last 2022
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 1 since 2021
YearPublicationVenuePosition
2022 On Covering Segments with Unit Intervals
abstract
We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in the unit interval. We also study several variants of this problem. We show that the restrictions of the aforementioned problems to the set of instances in which all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration. We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise.
Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
SIAM J. Discret. Math.1
2020 On Covering Segments with Unit Intervals
Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
STACS1