Grouped domination parameterized by vertex cover, twin cover, and beyond

DOI10.1016/J.TCS.2024.114507MaRDI QIDQ6131196zbMATH OpenFDO

Authors Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda

Publication date 4 April 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114507

zbMATH Keywords

dominating setgraph structural parameterspaired dominating setparameterized complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Parameterized Complexity of Generalized Domination Problems
• Parameterized complexity of generalized domination problems
• Parameterized Algorithms for Generalized Domination
• The parameterized complexity of dominating set and friends revisited for structured graphs
• Partial vs. Complete Domination: t-Dominating Set

Cites work

• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A survey of the algorithmic aspects of modular decomposition
• Algorithmic meta-theorems
• Algorithmic meta-theorems for restrictions of treewidth
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Complexity of paired domination in at-free and planar graphs
• Computing a minimum paired-dominating set in strongly orderable graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dominating sets for split and bipartite graphs
• Easy problems for tree-decomposable graphs
• Finding a dominating set on bipartite graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 1185309 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Labelling algorithms for paired-domination problems in block and interval graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the complexity of the disjoint paths problem
• Paired domination in graphs
• Paired-domination in graphs
• Paired-domination problem on distance-hereditary graphs
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Parameterized complexity of \((A,\ell)\)-path packing
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sparsity. Graphs, structures, and algorithms
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-width. I: Tractable FO model checking
• What makes equitable connected partition easy

Cited in

(1)

• Preprocessing complexity for some graph problems parameterized by structural parameters

This page was built for publication: Grouped domination parameterized by vertex cover, twin cover, and beyond

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