Show Book List

Reviews elsewhere on the web:
RONALD V. BOOK (pdf)
Everything2.com

M Garey and D Johnson

Computers and Intractability

Computers and intractability : a guide to the theory of NP-completeness by Michael R. Garey and David S. Johnson is a standard textbook for those interested in the theory of NP completeness.

This work is in three parts. The first introduces NP completeness and describes how to go about proving that a problem is NP complete. The second part looks at more advanced topics, such as the structure of the class of NP problems - you might think of all NP complete problems as being more or less the same, but the authors show that there is more it than that. They also describe tractable ways of obtaining approximate solutions to NP complete problems.

It's the third part which will be the most important for most people though. This consists of a list of a large number of NP complete problems including references to the proof of their NP completeness. So whether you are you are a student of computational complexity, you are thinking of attacking the million dollar P=NP question, or you just have to write a program for a problem which you think might be NP complete, you will find that this book is a useful addition to your library.

Amazon.com info
Paperback 340 pages  
ISBN: 0716710455
Salesrank: 275793
Weight:1.1 lbs
Published: 1979 W. H. Freeman
Amazon price $78.16
Marketplace:New from $62.69:Used from $40.99
Buy from Amazon.com
Amazon.co.uk info
Paperback 338 pages  
ISBN: 0716710455
Salesrank: 586533
Weight:1.1 lbs
Published: 1979 W. H. Freeman
Amazon price £53.99
Marketplace:New from £39.93:Used from £38.31
Buy from Amazon.co.uk
Amazon.ca info
Paperback
ISBN: 0716710455
Salesrank: 43945
Weight:1.1 lbs
Published: 1979 W H Freeman & Co
Marketplace:New from CDN$ 78.80:Used from CDN$ 51.95
Buy from Amazon.ca





Product Description
Book annotation not available for this title.
Title: Computers and Intractability
Author: Garey, Michael R./ Johnson, David S.
Publisher: Macmillan Higher Education
Publication Date: 1979/01/15
Number of Pages: 338
Binding Type: PAPERBACK
Library of Congress: 78012361