Node-Deletion NP-Complete Problems

Cited in

(36)

Combinatorial analysis (nonnegative matrices, algorithmic problems)
The node-deletion problem for hereditary properties is NP-complete
Combinatorial problems over power sets
A unified approximation algorithm for node-deletion problems
Fixed-parameter tractability of graph modification problems for hereditary properties
PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
The critical node detection problem in networks: a survey
On the NP-hardness of edge-deletion and -contraction problems
Approximation algorithm for minimum connected 3-path vertex cover
Approximation algorithms for minimum weight connected 3-path vertex cover
Polyhedral properties of the induced cluster subgraphs
Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
Approximation algorithms for minimum (weight) connected k-path vertex cover
Augmenting approach for some maximum set problems
Chordal editing is fixed-parameter tractable
On the hardness of energy minimisation for crystal structure prediction
A simple variant of node connectivity is NP-complete
On limitations of transformations between combinatorial problems
The \textsc{max quasi-independent set} problem
The approximation of maximum subgraph problems
Acyclic matchings in subclasses of bipartite graphs
PTAS for minimum \(k\)-path vertex cover in ball graph
scientific article; zbMATH DE number 7525474 (Why is no real title available?)
Connecting the dots (with minimum crossings)
A linear-time algorithm for finding induced planar subgraphs
The weighted k-path vertex cover problem on series-parallel graphs
Efficient stabilization of cooperative matching games
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Graph theory (algorithmic, algebraic, and metric problems)
On the hardness of energy minimisation for crystal structure prediction
Planarization of graphs embedded on surfaces
On the complexity of minimum maximal acyclic matchings
On the complexity of minimum maximal acyclic matchings
Reconfiguring planar perfect matchings via bounded length alternating cycles
On the descriptive complexity of vertex deletion problems
Edge-contraction problems

This page was built for publication: Node-Deletion NP-Complete Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3856812)