The complexity of dominating set in geometric intersection graphs
type: Item
instance of: scholarly article
title: The complexity of dominating set in geometric intersection graphs
zbMATH Open document ID: 1421.68071
author: Sándor Kisfaludi-Bak
author: Mark de Berg
author: Gerhard J. Woeginger
published in: Theoretical Computer Science
publication date: 2019-04-23T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7046889
zbMATH Keywords: dominating set
zbMATH Keywords: geometric intersection graph
zbMATH Keywords: W-hierarchy
zbMATH Keywords: semi-algebraic set
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.10.007
OpenAlex ID: W2896021245
cites work: Cylindrical Algebraic Decomposition I: The Basic Algorithm
cites work: Algorithms in real algebraic geometry
cites work: Q5452284
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Parameterized Algorithms
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Domination in Geometric Intersection Graphs
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Parametrized complexity theory.
cites work: Q4368729
cites work: Q4281651
cites work: Parameterized Complexity of Independence and Domination on Geometric Graphs
cites work: Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
DOI: 10.1016/J.TCS.2018.10.007
description: scientific article; zbMATH DE number 7046889