On the Parameterized Complexity of [1,j]-Domination Problems

DOI10.4230/LIPICS.FSTTCS.2018.34MaRDI QIDQ5090974OpenAlexFDO

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

Publication date 21 July 2022

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2018/9933/pdf/LIPIcs-FSTTCS-2018-34.pdf

zbMATH Keywords

sparse graphsparameterized complexity\([1,j\)-dominating set]

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• On the parameterized complexity of \([1,j]\)-domination problems
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Parameterized Complexity of Generalized Domination Problems
• Parameterized complexity of generalized domination problems
• FPT algorithms for domination in sparse graphs and beyond

Cites work

• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• Domination problems in nowhere-dense classes of graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• FPT algorithms for domination in biclique-free graphs
• First order properties on nowhere dense structures
• Fixed-Parameter Tractability and Completeness I: Basic Results
• 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
• Lossy kernels for connected dominating set on sparse graphs
• Mixed searching and proper-path-width
• On nowhere dense graphs
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• 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
• \((1, j)\)-set problem in graphs
• \([1,2]\)-domination in graphs
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• \([1,2]\)-sets in graphs

Cited in

(3)

• The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
• Parameterized Complexity of Generalized Domination Problems
• Domination above \(r\)-independence: does sparseness help?

This page was built for publication: On the Parameterized Complexity of [1,j]-Domination Problems

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