The dominating set problem in geometric intersection graphs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
28 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Titel12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's14:1-14:12
ISBN van geprinte versie978-3-95977-051-4
DOI's
StatusGepubliceerd - 1 feb 2018
Evenement12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Oostenrijk
Duur: 6 sep 20178 sep 2017
Congresnummer: 12
https://algo2017.ac.tuwien.ac.at/ipec

Publicatie series

NaamLIPIcs
Volume89

Congres

Congres12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Verkorte titelIPEC 2017
LandOostenrijk
StadVienna
Periode6/09/178/09/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'The dominating set problem in geometric intersection graphs'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    De Berg, M., Kisfaludi-Bak, S., & Woeginger, G. (2018). The dominating set problem in geometric intersection graphs. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 (blz. 14:1-14:12). (LIPIcs; Vol. 89). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2017.14