The dominating set problem in geometric intersection graphs
- ,
- Sándor Kisfaludi-Bak,
- Gerhard Woeginger
- ,
- ,
- RWTH Aachen University
Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-reviewOpen access
Information
Output type
Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 14:1-14:12Publication milestones
- Published - 01/02/2018
Publication status
Published - 01/02/2018
Place of publication
DagstuhlPublisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikPublication series
- Publication series name: LIPIcs
Volume: 89
ISBN (Print)
978-3-95977-051-4Host publication title
12th International Symposium on Parameterized and Exact Computation, IPEC 2017Related Event
Title
12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Event type
ConferenceDegree of recognition
International eventDate
06/09/2017 - 08/09/2017Location
ViennaAustria
Abstract
<p>We study the parameterized complexity of dominating sets in geometric intersection graphs. • In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). • In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.</p>
Documents and Links
Final published version, 782.79 KB
Metrics
Metrics
SciVal
citations
1
SciVal
FWCI
0.09
SciVal
Author count
3
SciVal
Paper percentile
28
Download statistics
Download count
472
Scopus
citations
1
PlumX, opens in new tab
Citation count
1
Captures
2
