Perfect domination and small cycles

DOI10.1142/S1793830917500306MaRDI QIDQ5367522zbMATH OpenOpenAlexFDO

Authors Yong Zhang, Minghui Jiang

Publication date 20 October 2017

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830917500306

zbMATH Keywords

graph dominationparameterized complexityperfect code

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• The kernelization complexity of connected domination in graphs with (no) small cycles
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Triangles, 4-Cycles and Parameterized (In-)Tractability
• Perfect graphs of strong domination and independent strong domination
• The effect of girth on the kernelization complexity of connected dominating set

Cites work

• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Dominating set is fixed parameter tractable in claw-free graphs
• Dominating sets in n‐cubes
• Domination problems in nowhere-dense classes of graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Independent domination in chordal graphs
• Kernelization of edge perfect code and its variants
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• On the parameterized complexity of multiple-interval graph problems
• Parameterized approximation of dominating set problems
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Perfect Code is \(W[1]\)-complete
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• The kernelization complexity of connected domination in graphs with (no) small cycles
• The weighted perfect domination problem
• Weighted efficient domination problem on some perfect graphs

Cited in

(5)

• Perfect matching dominating cycle — a new dominating cycle
• Triangles, 4-Cycles and Parameterized (In-)Tractability
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• The kernelization complexity of connected domination in graphs with (no) small cycles

This page was built for publication: Perfect domination and small cycles

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