scientific article; zbMATH DE number 30298

MaRDI QIDQ3985346zbMATH OpenFDO

Authors Satoru Miyano

Publication date 27 June 1992

zbMATH Keywords

edge deletionlexicographically first maximal subgraphNP-completenessseries-parallel graphsvertex deletion

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Node-and edge-deletion NP-complete problems
• On the complexity of some subgraph problems
• On the complexity of the maximum subgraph problem
• EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
• Ordered vertex removal and subgraph problems

Cited in

(9)

• An appraisal of the performance of the MMSC subgraph generation algorithm on a Cyber system 170/720
• Approximations for the maximum acyclic subgraph problem
• The Complexity of Acyclic Subhypergraph Problems
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• scientific article; zbMATH DE number 803996 (Why is no real title available?)
• On the complexity of the maximum subgraph problem
• Ordered vertex removal and subgraph problems
• Sublinear P system solutions to NP-complete problems
• On the complexity of some subgraph problems

This page was built for publication:

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