Parameterized complexity of generalized domination problems

DOI10.1016/J.DAM.2010.11.012zbMATH Open1241.05108OpenAlexW2064310439MaRDI QIDQ415279FDOQ415279

Authors Petr A. Golovach, Ondřej Suchý, Jan Kratochvíl

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.11.012

zbMATH Keywords

parameterized complexityeven setgeneralized dominationodd set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Parameterized Complexity of Generalized Domination Problems
• scientific article; zbMATH DE number 1202982
• Sort and Search: exact algorithms for generalized domination
• The parameterized complexity of domination-type problems and application to linear codes
• Parameterized Algorithms for Generalized Domination

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 794265 (Why is no real title available?)
• scientific article; zbMATH DE number 921905 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Faster algorithms on branch and clique decompositions
• First order properties on nowhere dense structures
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Mod-2 independence and domination in graphs
• On nowhere dense graphs
• On the Boolean-width of a graph: structure and applications
• Parameterized Complexity of Generalized Domination Problems
• Parametrized complexity theory.
• Perfect Code is \(W[1]\)-complete
• Sort and Search: exact algorithms for generalized domination
• The Grad of a Graph and Classes with Bounded Expansion
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Threshold dominating sets and an improved characterization of \(W[2]\)

Cited in

(25)

• The complexity of finding harmless individuals in social networks
• Parameterized complexity of weak odd domination problems
• An integer programming approach for solving a generalized version of the Grundy domination number
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Combinatorial properties of a general domination problem with parity constraints
• Parameterized Complexity of Generalized Domination Problems
• On the Parameterized Complexity of Approximating Dominating Set
• Parameterized Algorithms for Generalized Domination
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Sort and Search: exact algorithms for generalized domination
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Branch and Recharge: Exact Algorithms for Generalized Domination
• Parameterized Complexity of DPLL Search Procedures
• Partial vs. Complete Domination: t-Dominating Set
• Parameterized complexity in multiple-interval graphs: domination
• On the parameterized complexity of \([1,j]\)-domination problems
• On the Parameterized Complexity of [1,j]-Domination Problems
• scientific article; zbMATH DE number 794265 (Why is no real title available?)
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Structural parameterizations of the mixed Chinese postman problem
• The parameterized complexity of domination-type problems and application to linear codes
• Subexponential fixed-parameter algorithms for partial vector domination

This page was built for publication: Parameterized complexity of generalized domination problems

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