On the NP-hardness of edge-deletion and -contraction problems
type: Item
instance of: scholarly article
title: On the NP-hardness of edge-deletion and -contraction problems
zbMATH Open document ID: 0511.68028
DOI: 10.1016/0166-218X(83)90101-4
author: Yanyan Li
published in: Discrete Applied Mathematics
publication date: 1983-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3806934
zbMATH Keywords: edge-deletion
zbMATH Keywords: edge-contraction
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q3941433
cites work: The complexity of theorem-proving procedures
cites work: Q3883524
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: `` Strong '' NP-Completeness Results
cites work: Parallel concepts in graph theory
cites work: Dividing a Graph into Triconnected Components
cites work: Q4142699
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Node-Deletion NP-Complete Problems
cites work: Q4144192
cites work: On the removal of forbidden graphs by edge-deletion or by edge- contraction
cites work: Node-and edge-deletion NP-complete problems
cites work: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
full work available at URL: 0166-218x(83)90101-4
OpenAlex ID: W2022137727
description: scientific article; zbMATH DE number 3806934