Perfect domination and small cycles

DOI10.1142/S1793830917500306zbMATH Open1373.05141OpenAlexW2593365144MaRDI QIDQ5367522FDOQ5367522

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

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On the parameterized complexity of multiple-interval graph problems
• The weighted perfect domination problem
• Title not available (Why is that?)
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Weighted efficient domination problem on some perfect graphs
• Perfect Code is \(W[1]\)-complete
• Domination problems in nowhere-dense classes of graphs
• Kernelization of edge perfect code and its variants
• Title not available (Why is that?)
• Dominating sets in n‐cubes
• Independent domination in chordal graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Parameterized approximation of dominating set problems
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• 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
• Dominating set is fixed parameter tractable in claw-free graphs

Cited In (5)

• Triangles, 4-Cycles and Parameterized (In-)Tractability
• 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
• Perfect matching dominating cycle — a new dominating cycle
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

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)