The Dominating Set Problem in Geometric Intersection Graphs
From MaRDI portal
Publication:5111873
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
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