The complexity of some edge deletion problems
From MaRDI portal
Publication:3801094
Recommendations
- scientific article; zbMATH DE number 4089594
- Node-and edge-deletion NP-complete problems
- An Application of Duality to Edge-Deletion Problems
- EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
- Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
Cited in
(49)- Edge deletion preserving the diameter of the hypercube
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Characterizing and computing minimal cograph completions
- scientific article; zbMATH DE number 2230201 (Why is no real title available?)
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- On the complexity of some subgraph problems
- NP-completeness results for edge modification problems
- Hardness of edge-modification problems
- Additive approximation of generalized Turán questions
- Node-and edge-deletion NP-complete problems
- Linear optimization over homogeneous matrix cones
- Edge deletion problems: branching facilitated by modular decomposition
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Cutting a tree with subgraph complementation is hard, except for some small trees
- On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
- How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks
- Cutting a tree with subgraph complementation is hard, except for some small trees
- A Polynomial Kernel for Line Graph Deletion
- scientific article; zbMATH DE number 4089594 (Why is no real title available?)
- A Polynomial Kernel for Diamond-Free Editing
- Finding the root graph through minimum edge deletion
- A Note on the Minimum H-Subgraph Edge Deletion
- On the flora of asynchronous locally non-monotonic Boolean automata networks
- Additive approximation for edge-deletion problems
- Characterizing and Computing Minimal Cograph Completions
- Complexity classification of some edge modification problems
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- On the sizes of generalized cactus graphs
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Complexity of modification problems for best match graphs
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- An Application of Duality to Edge-Deletion Problems
- On the complexity of singly connected vertex deletion
- Testing outerplanarity of bounded degree graphs
- Trimming forests is hard (unless they are made of stars)
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- scientific article; zbMATH DE number 7278081 (Why is no real title available?)
- A polynomial kernel for diamond-free editing
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Tree-edges deletion problems with bounded diameter obstruction sets
- Complexity and parameterized algorithms for cograph editing
- Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
- Parameterized vertex deletion problems for hereditary graph classes with a block property
- Orthology relation and gene tree correction: complexity results
- Edge deletion to tree-like graph classes
- Efficient stabilization of cooperative matching games
This page was built for publication: The complexity of some edge deletion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3801094)
