Parameterized complexity of generalized domination problems
From MaRDI portal
Publication:415279
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
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
- Linear time solvable optimization problems on graphs of bounded clique-width
- 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
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Perfect Code is \(W[1]\)-complete
- Faster algorithms on branch and clique decompositions
- Title not available (Why is that?)
- Title not available (Why is that?)
- On nowhere dense graphs
- First order properties on nowhere dense structures
- On the Boolean-width of a graph: structure and applications
- Title not available (Why is that?)
- Threshold dominating sets and an improved characterization of \(W[2]\)
- The Grad of a Graph and Classes with Bounded Expansion
- Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- MOD-2 INDEPENDENCE AND DOMINATION IN GRAPHS
- Parameterized Complexity of Generalized Domination Problems
- Sort and Search: exact algorithms for generalized domination
Cited In (21)
- Parameterized Complexity of DPLL Search Procedures
- On the Parameterized Complexity of Approximating Dominating Set
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- Parameterized Complexity of Generalized Domination Problems
- A width parameter useful for chordal and co-comparability graphs
- Partial vs. Complete Domination: t-Dominating Set
- Parameterized complexity in multiple-interval graphs: domination
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
- Subexponential fixed-parameter algorithms for partial vector domination
- Sort and Search: exact algorithms for generalized domination
- Branch and Recharge: Exact Algorithms for Generalized Domination
- Structural Parameterizations of the Mixed Chinese Postman Problem
- Parameterized Algorithms for Generalized Domination
- The complexity of finding harmless individuals in social networks
- An integer programming approach for solving a generalized version of the Grundy domination number
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- Combinatorial properties of a general domination problem with parity constraints
- Title not available (Why is that?)
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)
