The Dominating Set Problem in Geometric Intersection Graphs

DOI10.4230/LIPIcs.IPEC.2017.14zbMath1443.68126arXiv1709.05182OpenAlexW2964281516MaRDI QIDQ5111873

Gerhard J. Woeginger, Sándor Kisfaludi-Bak, Mark T. de Berg

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1709.05182

zbMATH Keywords

intersection graphdominating setW-hierarchy

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• The complexity of dominating set in geometric intersection graphs
• Parametrized complexity theory.
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results