On the parameterized complexity of \([1,j]\)-domination problems

DOI10.1016/j.tcs.2019.11.032zbMath1436.68147OpenAlexW2991587872MaRDI QIDQ2283043

Fahad Panolan, Fedor V. Fomin, Amer E. Mouawad, Mohsen Alambardar Meybodi

Publication date: 27 December 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.11.032

zbMATH Keywords

parameterized complexitysparse graphstotal dominating setrestrained dominating set\([1, j\)-dominating set]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Parameterized complexity of minimum membership dominating set ⋮ Parameterized complexity of minimum membership dominating set ⋮ On \([j, k\)-sets in graphs]

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \((1, j)\)-set problem in graphs
• \([1,2\)-domination in graphs]
• Sparsity. Graphs, structures, and algorithms
• Mixed searching and proper-path-width
• \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms]
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• On the parameterized complexity of multiple-interval graph problems
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Restrained domination in graphs
• Total \([1,2\)-domination in graphs]
• 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
• On nowhere dense graphs
• \([1,2\)-sets in graphs]
• FPT Algorithms for Domination in Biclique-Free Graphs
• Domination Problems in Nowhere-Dense Classes
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Deciding First-Order Properties of Nowhere Dense Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• First order properties on nowhere dense structures
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms

This page was built for publication: On the parameterized complexity of \([1,j]\)-domination problems