Two edge modification problems without polynomial kernels
From MaRDI portal
Recommendations
- Two edge modification problems without polynomial kernels
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Incompressibility of \(H\)-free edge modification
- On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
Cites work
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- A more effective linear kernelization for cluster editing
- Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15--17, 2007. Proceedings.
- Complexity classification of some edge modification problems
- Cross-composition: a new technique for kernelization lower bounds
- Fast FPT-Algorithms for Cleaning Grids
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization Algorithms for d-Hitting Set Problems
- Kernelization Lower Bounds by Cross-Composition
- Kernelization and Complexity Results for Connectivity Augmentation Problems
- NP-completeness results for edge modification problems
- On generating triangle-free graphs
- On problems without polynomial kernels
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Parametrized complexity theory.
- Preprocessing of min ones problems: a dichotomy
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Some consequences of non-uniform conditions on uniform classes
- Two edge modification problems without polynomial kernels
Cited in
(30)- (Sub)linear kernels for edge modification problems toward structured graph classes
- Cutting a tree with subgraph complementation is hard, except for some small trees
- A completeness theory for polynomial (Turing) kernelization
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- A Polynomial Kernel for Line Graph Deletion
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- Win-win kernelization for degree sequence completion problems
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- Parameterized aspects of strong subgraph closure
- Exploring the subexponential complexity of completion problems
- Two edge modification problems without polynomial kernels
- On the parameterized complexity of graph modification to first-order logic properties
- Parameterized aspects of strong subgraph closure
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- A survey of parameterized algorithms and the complexity of edge modification
- Cutting a tree with subgraph complementation is hard, except for some small trees
- Kernelization of edge perfect code and its variants
- Incompressibility of \(H\)-free edge modification problems
- A Polynomial Kernel for Diamond-Free Editing
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- scientific article; zbMATH DE number 7764101 (Why is no real title available?)
- Polynomial kernels for paw-free edge modification problems
- Win-win kernelization for degree sequence completion problems
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
- Incompressibility of \(H\)-free edge modification
This page was built for publication: Two edge modification problems without polynomial kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662097)
