Perfect domination and small cycles
DOI10.1142/S1793830917500306zbMATH Open1373.05141OpenAlexW2593365144MaRDI QIDQ5367522FDOQ5367522
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- 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
- 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 (2)
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)
