A polynomial kernel for diamond-free editing
From MaRDI portal
Recommendations
- A Polynomial Kernel for Diamond-Free Editing
- Parameterized lower bound and improved kernel for diamond-free edge deletion
- Two edge modification problems without polynomial kernels
- On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
- Incompressibility of \(H\)-free edge modification problems
Cites work
- A kernelization algorithm for \(d\)-hitting set
- Cluster editing: kernelization based on edge cuts
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Hardness of approximation for \(H\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems
- Intersection Theorems for Systems of Sets
- Node-Deletion Problems on Bipartite Graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- On the complexity of \(k\)-SAT
- Parameterized lower bound and improved kernel for diamond-free edge deletion
- Parametrized complexity theory.
- Polynomial kernels for paw-free edge modification problems
- The complexity of some edge deletion problems
- The node-deletion problem for hereditary properties is NP-complete
- Two edge modification problems without polynomial kernels
Cited in
(7)- Cutting a tree with subgraph complementation is hard, except for some small trees
- Cutting a tree with subgraph complementation is hard, except for some small trees
- A Polynomial Kernel for Diamond-Free Editing
- Parameterized lower bound and improved kernel for diamond-free edge deletion
- A survey of parameterized algorithms and the complexity of edge modification
- Polynomial kernelization for removing induced claws and diamonds
- Polynomial kernelization for removing induced claws and diamonds
This page was built for publication: A polynomial kernel for diamond-free editing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2072105)