The complexity of dominating set in geometric intersection graphs
From MaRDI portal
Publication:1737591
DOI10.1016/j.tcs.2018.10.007zbMath1421.68071OpenAlexW2896021245MaRDI QIDQ1737591
Sándor Kisfaludi-Bak, Mark T. de Berg, Gerhard J. Woeginger
Publication date: 23 April 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.10.007
Analysis of algorithms and problem complexity (68Q25) 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)
Related Items
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, On dominating set of some subclasses of string graphs, Hyperideal-based intersection graphs, On Geometric Set Cover for Orthants, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, The Dominating Set Problem in Geometric Intersection Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- On the parameterized complexity of multiple-interval graph problems
- 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
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- Domination in Geometric Intersection Graphs
- Parameterized Algorithms
- Algorithms in real algebraic geometry
