Reducibility Among Combinatorial Problems
twenty-one problems reduced to one another, making NP-completeness a tool
Read it
EnglishTiếng Việt (abstract only)中文 (abstract only)日本語 (abstract only)
English beside Tiếng ViệtEnglish beside 中文English beside 日本語
- 24 sections
- 0 figures
- 0 equations
- 8 references
- cited by 1 here
- difficulty 4 of 5
- the publisher's page
Contents
- 1INTRODUCTION
- 2THE CLASS $P$
- 3NONDETERMINISTIC ALGORITHMS AND COOK'S THEOREM
- 4COMPLETE PROBLEMS
- 5NODE COVER
- 6SET COVERING
- 7FEEDBACK NODE SET
- 8FEEDBACK ARC SET
- 9DIRECTED HAMILTON CIRCUIT
- 10UNDIRECTED HAMILTON CIRCUIT
- 11SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE
- 12CHROMATIC NUMBER
- 13CLIQUE COVER
- 14EXACT COVER
- 15HITTING SET
- 16STEINER TREE
- 173-DIMENSIONAL MATCHING
- 18KNAPSACK
- 19JOB SEQUENCING
- 20PARTITION
- 21MAX CUT
- Appendix I
Its place here
- cited byNew Directions in Cryptography