Node-and edge-deletion NP-complete problems
type: Item
instance of: scholarly article
title: Node-and edge-deletion NP-complete problems
zbMATH Open document ID: 1282.68131
DOI: 10.1145/800133.804355
author: Mihalis Yannakakis
published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78
publication date: 2014-03-14T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6270125
zbMATH Keywords: approximation
zbMATH Keywords: computational complexity
zbMATH Keywords: edge-deletion
zbMATH Keywords: graph
zbMATH Keywords: graph-property
zbMATH Keywords: hereditary
zbMATH Keywords: maximum subgraph
zbMATH Keywords: NP-complete
zbMATH Keywords: node-deletion
zbMATH Keywords: polynomial hierarchy
Wikidata QID: Q56209809
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1145/800133.804355
OpenAlex ID: W2045027193
DBLP publication ID: conf/stoc/Yannakakis78
Recommended article: The complexity of some edge deletion problems
Recommended article: Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
Recommended article: Tractability of König edge deletion problems
Recommended article: Approximating power node-deletion problems
Recommended article: NP-completeness of some edge-disjoint paths problems
Recommended article: A new approach for approximating node deletion problems
Recommended article: A unified approximation algorithm for node-deletion problems
Recommended article: Edge deletion problems: branching facilitated by modular decomposition
Recommended article: Vertex deletion problems on chordal graphs
Recommended article: Vertex Deletion Problems on Chordal Graphs
description: scientific article; zbMATH DE number 6270125