On the (non-)existence of polynomial kernels for P _l -free edge modification problems
From MaRDI portal
Publication:1949740
Recommendations
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Two edge modification problems without polynomial kernels
- Two edge modification problems without polynomial kernels
- Incompressibility of H-free edge modification
- Incompressibility of \(H\)-free edge modification problems
Cites work
- A \(2k\) kernel for the cluster editing problem
- A 4k^2 kernel for feedback vertex set
- A Combinatorial Decomposition Theory
- A general method to speed up fixed-parameter-tractable algorithms
- A survey of the algorithmic aspects of modular decomposition
- An O(n2) Algorithm for Undirected Split Decomposition
- Cluster graph modification problems
- Cograph editing: complexity and parameterized algorithms
- Complexity classification of some edge modification problems
- Cross-composition: a new technique for kernelization lower bounds
- Deterministic pivoting algorithms for constrained ranking and clustering problems
- Efficient Parameterized Preprocessing for Cluster Editing
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph Classes: A Survey
- Graph Sandwich Problems
- Graph-Theoretic Concepts in Computer Science
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 5485441 (Why is no real title available?)
- scientific article; zbMATH DE number 5485472 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernels for feedback arc set in tournaments
- On generating triangle-free graphs
- On problems without polynomial kernels
- Parametrized complexity theory.
- Polynomial kernels for 3-leaf power graph modification problems
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The complexity of some edge deletion problems
- Two edge modification problems without polynomial kernels
Cited in
(42)- Two edge modification problems without polynomial kernels
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- On subgraph complementation to \(H\)-free Graphs
- (Sub)linear kernels for edge modification problems toward structured graph classes
- Linear-time minimal cograph editing
- On the parameterized complexity of graph modification to first-order logic properties
- Incompressibility of \(H\)-free edge modification problems
- Polynomial kernelization for removing induced claws and diamonds
- A cubic-vertex kernel for flip consensus tree
- Parameterized algorithms for edge biclique and related problems
- Kernel for \(K_t\)\textsc-free Edge Deletion
- On subgraph complementation to \(H\)-free graphs
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- On the computational complexity of the bipartizing matching problem
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Polynomial kernelization for removing induced claws and diamonds
- Exploring the subexponential complexity of completion problems
- Incompressibility of H-free edge modification
- On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Two edge modification problems without polynomial kernels
- Fractals for kernelization lower bounds
- An effective branching strategy for some parameterized edge modification problems with multiple forbidden induced subgraphs
- A Polynomial Kernel for Diamond-Free Editing
- Cograph editing: Merging modules is equivalent to editing P₄s
- A Polynomial Kernel for Line Graph Deletion
- Incompressibility of H-free edge modification problems: towards a dichotomy
- Polynomial kernels for paw-free edge modification problems
- Polynomial kernels for 3-leaf power graph modification problems
- scientific article; zbMATH DE number 7764101 (Why is no real title available?)
- A survey of parameterized algorithms and the complexity of edge modification
- 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 quasi-quadratic vertex-kernel for cograph edge editing
- An improved kernelization algorithm for trivially perfect editing
- A quadratic vertex kernel for diamond-free edge deletion
- Polynomial kernels for edge modification problems towards block and strictly chordal graphs
- Polynomial kernel and incompressibility for prison-free edge deletion and completion
- Kernelization of compressing two-dimensional routing tables with order
- On the effectiveness of the incremental approach to minimal chordal edge modification
This page was built for publication: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1949740)
