Node-Deletion NP-Complete Problems
From MaRDI portal
Publication:3856812
DOI10.1137/0208049zbMath0423.05039OpenAlexW2012931553MaRDI QIDQ3856812
Narsingh Deo, Mukkai S. Krishnamoorthy
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0208049
bipartitetreeintervalHamiltonianouterplanarplanarNP-completecompletetransitiveacyclicnonseparablechordalnulldegree-constrainednode coverline invertiblenode-delectionsingleton K-basistransitively orientablewithout cycles of a specified length
Related Items (34)
Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Augmenting approach for some maximum set problems ⋮ Chordal editing is fixed-parameter tractable ⋮ On limitations of transformations between combinatorial problems ⋮ Fixed-parameter tractability of graph modification problems for hereditary properties ⋮ Unnamed Item ⋮ Parameterized complexity of fair deletion problems ⋮ The node-deletion problem for hereditary properties is NP-complete ⋮ Combinatorial problems over power sets ⋮ Planarization of graphs embedded on surfaces ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ On the complexity of minimum maximal acyclic matchings ⋮ The \textsc{max quasi-independent set} problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ A simple variant of node connectivity is NP-complete ⋮ The approximation of maximum subgraph problems ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ The critical node detection problem in networks: a survey ⋮ Efficient stabilization of cooperative matching games ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ Unnamed Item ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ A unified approximation algorithm for node-deletion problems ⋮ Connecting the dots (with minimum crossings) ⋮ On the NP-hardness of edge-deletion and -contraction problems ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Edge-contraction problems ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs
This page was built for publication: Node-Deletion NP-Complete Problems
