MNP: A class of NP optimization problems

DOI10.1007/BF02943150MaRDI QIDQ1368182zbMATH OpenFDO

Authors Qi Cheng, Hong Zhu, Hong Zhu

Publication date 28 September 1997

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02943150

zbMATH Keywords

NP classoptimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorics in computer science (68R05)

Recommendations

• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 4155842
• scientific article; zbMATH DE number 1944142
• scientific article; zbMATH DE number 861333
• Minimization and \(\mathbf{NP}\) multifunctions
• On approximating NP-hard optimization problems
• Approximate solution of NP optimization problems
• On fixed-parameter tractability and approximability of NP optimization problems
• Approximation properties of NP minimization classes

Cites work

• Approximating maximum independent sets by excluding subgraphs
• Efficient probabilistically checkable proofs and applications to approximations
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Optimization, approximation, and complexity classes
• The directed subgraph homeomorphism problem

Cited in

(2)

• MPF problem over modified medial semigroup is NP-complete
• MNP: A class of NP optimization problems

This page was built for publication: MNP: A class of NP optimization problems

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