On Covering Segments with Unit Intervals. / Bergren, Dan; Eiben, Eduard; Ganian, Robert; Kanj, Iyad.

2020. 13:1-13:17 Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France.

Research output: Contribution to conferencePaperpeer-review

Published

Standard

On Covering Segments with Unit Intervals. / Bergren, Dan; Eiben, Eduard; Ganian, Robert; Kanj, Iyad.

2020. 13:1-13:17 Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France.

Research output: Contribution to conferencePaperpeer-review

Harvard

Bergren, D, Eiben, E, Ganian, R & Kanj, I 2020, 'On Covering Segments with Unit Intervals', Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France, 10/03/20 - 13/03/20 pp. 13:1-13:17. https://doi.org/10.4230/LIPIcs.STACS.2020.13

APA

Bergren, D., Eiben, E., Ganian, R., & Kanj, I. (2020). On Covering Segments with Unit Intervals. 13:1-13:17. Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France. https://doi.org/10.4230/LIPIcs.STACS.2020.13

Vancouver

Bergren D, Eiben E, Ganian R, Kanj I. On Covering Segments with Unit Intervals. 2020. Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France. https://doi.org/10.4230/LIPIcs.STACS.2020.13

Author

Bergren, Dan ; Eiben, Eduard ; Ganian, Robert ; Kanj, Iyad. / On Covering Segments with Unit Intervals. Paper presented at The 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France.17 p.

BibTeX

@conference{7fabc67e1cae42d1991a4ef25518a0b1,
title = "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.",
author = "Dan Bergren and Eduard Eiben and Robert Ganian and Iyad Kanj",
year = "2020",
month = feb,
day = "27",
doi = "10.4230/LIPIcs.STACS.2020.13",
language = "English",
pages = "13:1--13:17",
note = "The 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 ; Conference date: 10-03-2020 Through 13-03-2020",
url = "https://stacs2020.sciencesconf.org/",

}

RIS

TY - CONF

T1 - On Covering Segments with Unit Intervals

AU - Bergren, Dan

AU - Eiben, Eduard

AU - Ganian, Robert

AU - Kanj, Iyad

PY - 2020/2/27

Y1 - 2020/2/27

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.STACS.2020.13

DO - 10.4230/LIPIcs.STACS.2020.13

M3 - Paper

SP - 13:1-13:17

T2 - The 37th International Symposium on Theoretical Aspects of Computer Science

Y2 - 10 March 2020 through 13 March 2020

ER -