Node-Deletion NP-Complete Problems

Cited in

(36)

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

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)