The complexity of dominating set in geometric intersection graphs

DOI10.1016/J.TCS.2018.10.007MaRDI QIDQ1737591zbMATH OpenOpenAlexFDO

Authors Sándor Kisfaludi-Bak, Mark 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

zbMATH Keywords

dominating setsemi-algebraic setgeometric intersection graphW-hierarchy

Mathematics Subject Classification ID

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)

Recommendations

• The dominating set problem in geometric intersection graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Domination in Geometric Intersection Graphs
• Parameterized complexity in multiple-interval graphs: domination
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy

Cites work

• scientific article; zbMATH DE number 512936 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Computational geometry. Algorithms and applications.
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• Domination in Geometric Intersection Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On the parameterized complexity of multiple-interval graph problems
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parameterized algorithms
• Parametrized complexity theory.
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

Cited in

(11)

• Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
• The dominating set problem in geometric intersection graphs
• Tractabilities and intractabilities on geometric intersection graphs
• On dominating set of some subclasses of string graphs
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs.
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• On Geometric Set Cover for Orthants
• Geometric dominating-set and set-cover via local-search
• Hyperideal-based intersection graphs
• Geometric dominating sets -- a minimum version of the no-three-in-line problem

This page was built for publication: The complexity of dominating set in geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1737591)