Kernelization of edge perfect code and its variants

DOI10.1016/J.DAM.2016.06.013zbMATH Open1346.05216OpenAlexW2474647057MaRDI QIDQ317422FDOQ317422

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

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

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)

Cites Work

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

Cited In (2)

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

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)