NP-completeness results for edge modification problems
From MaRDI portal
Publication:2500532
Recommendations
- Publication:4944968
- Parameterized lower bounds and dichotomy results for the NP-completeness of \(H\)-free edge modification problems
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Graph modification problem for some classes of graphs
- Node-and edge-deletion NP-complete problems
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1107738 (Why is no real title available?)
- scientific article; zbMATH DE number 2096438 (Why is no real title available?)
- scientific article; zbMATH DE number 1409177 (Why is no real title available?)
- scientific article; zbMATH DE number 2188345 (Why is no real title available?)
- scientific article; zbMATH DE number 6472574 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- scientific article; zbMATH DE number 2230201 (Why is no real title available?)
- Algorithms for weakly triangulated graphs
- Bicliques in graphs. I: Bounds on their number
- Clique Graphs of Chordal and Path Graphs
- Complexity classification of some edge modification problems
- Computing the Minimum Fill-In is NP-Complete
- Coordinated graphs and clique graphs of clique-Helly perfect graphs
- Edge-Deletion Problems
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Linear-time recognition of circular-arc graphs
- On intervalizing \(k\)-colored graphs for DNA physical mapping
- On local convexity in graphs
- On the complexity of DNA physical mapping
- Orienting graphs to optimize reachability
- Polynomial time recognition of unit circular-arc graphs
- Recognition of Circle Graphs
- Recognizing Berge graphs
- Representation of a finite graph by a set of intervals on the real line
- Some complexity results about threshold graphs
- Some simplified NP-complete graph problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The complexity of some edge deletion problems
- The splittance of a graph
Cited in
(42)- An NP-completeness result of edge search in graphs
- (Sub)linear kernels for edge modification problems toward structured graph classes
- Editing to Eulerian graphs
- Complexity and parameterized algorithms for cograph editing
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Indirect identification of horizontal gene transfer
- Two edge modification problems without polynomial kernels
- On the computational complexity of the bipartizing matching problem
- Graph editing to a fixed target
- Reducing rank of the adjacency matrix by graph modification
- Blockers and transversals
- Exact-2-relation graphs
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Editing to a planar graph of given degrees
- Efficient algorithms for Eulerian extension
- NP-completeness for minimizing maximum edge length in grid embeddings
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- scientific article; zbMATH DE number 1420899 (Why is no real title available?)
- Reducing rank of the adjacency matrix by graph modification
- Editing to a planar graph of given degrees
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Critical edges for the assignment problem: complexity and exact resolution
- Biclique-Helly graphs
- Exploring the subexponential complexity of completion problems
- Two edge modification problems without polynomial kernels
- Characterizing and computing minimal cograph completions
- Graph modification problem for some classes of graphs
- A cubic-vertex kernel for flip consensus tree
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Parameterized complexity of Eulerian deletion problems
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
- Switches in Eulerian graphs
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized complexity of Eulerian deletion problems
- Matching interdiction
- Editing to a connected graph of given degrees
- Characterizing and Computing Minimal Cograph Completions
- MPF problem over modified medial semigroup is NP-complete
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
This page was built for publication: NP-completeness results for edge modification problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500532)
