1 Search Results for "Bergren, Dan"

Document

DOI: 10.4230/LIPIcs.STACS.2020.13

On Covering Segments with Unit Intervals

Authors: Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

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.

Cite as

Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj. On Covering Segments with Unit Intervals. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bergren_et_al:LIPIcs.STACS.2020.13,
  author =	{Bergren, Dan and Eiben, Eduard and Ganian, Robert and Kanj, Iyad},
  title =	{{On Covering Segments with Unit Intervals}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.13},
  URN =		{urn:nbn:de:0030-drops-118741},
  doi =		{10.4230/LIPIcs.STACS.2020.13},
  annote =	{Keywords: Segment covering, unit intervals, NP-completeness, parameterized complexity}
}

Refine by Author
1 Bergren, Dan
1 Eiben, Eduard
1 Ganian, Robert
1 Kanj, Iyad

Refine by Classification
1 Theory of computation → Computational geometry
1 Theory of computation → Parameterized complexity and exact algorithms

Refine by Keyword
1 NP-completeness
1 Segment covering
1 parameterized complexity
1 unit intervals

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Bergren, Dan"

On Covering Segments with Unit Intervals

Abstract

Cite as

Thanks for your feedback!

Could not send message