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 setgeometric intersection graphsemi-algebraic setW-hierarchy

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

• 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
• scientific article; zbMATH DE number 512936 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parametrized complexity theory.
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

Cited in

(13)

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

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)