Kernelization of edge perfect code and its variants

DOI10.1016/J.DAM.2016.06.013MaRDI QIDQ317422zbMATH OpenOpenAlexFDO

Authors Yong Zhang, Minghui Jiang

Publication date 30 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.06.013

zbMATH Keywords

parameterized complexitykernelizationperfect code

Mathematics Subject Classification ID

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

• scientific article; zbMATH DE number 4070305
• Kernels for edge dominating set: simpler or smaller
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

Cites work

• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• A note on the NP-hardness of two matching problems in induced subgrids
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Domination problems in nowhere-dense classes of graphs
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• Exact algorithms for dominating induced matching based on graph partition
• Fast algorithms for some dominating induced matching problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Hamilton Paths in Grid Graphs
• Incompressibility through Colors and IDs
• Kernel bounds for disjoint cycles and disjoint paths
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• New parameterized algorithms for the edge dominating set problem
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect Code is \(W[1]\)-complete
• Perfect codes in graphs
• Perfect edge domination and efficient edge domination in graphs
• Planar graph vertex partition for linear problem kernels
• Proofs from THE BOOK
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• The parameterized complexity of the induced matching problem
• Weighted efficient domination problem on some perfect graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(2)

• Edge local complementation and equivalence of binary linear codes
• Perfect domination and small cycles

This page was built for publication: Kernelization of edge perfect code and its variants

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