Computers and Intractability: A Guide to the Theory of NP-Completeness
En ciencias de la computación, más específicamente en el área de complejidad computacional, Computers and Intractability: A Guide to the Theory of NP-Completeness es un influyente libro de texto escrito por Michael Garey y David S. Johnson.
| Computers and Intractability: A Guide to the Theory of NP-Completeness | ||
|---|---|---|
| de Michael Garey y David S. Johnson | ||
| Género | Libro de texto | |
| Tema(s) | Ciencias de la computación | |
| Idioma | Inglés | |
| Título original | Computers and Intractability: A Guide to the Theory of NP-Completeness | |
| Editorial | W.H. Freeman y Cía. | |
| País | Estados Unidos | |
| Fecha de publicación | 1979 | |
| Formato | Impreso | |
Fue el primer libro en tratar formalmente la NP-completitud y la intratabilidad.[1] El libro contiene un apéndice que provee un exhaustivo compendio de problemas de NP-completitud, el cual ha sido actualizado en las reimpresiones del libro. Actualmente se encuentra desactualizado en algunos aspectos, como el desarrollo del reciente teorema PCP, tema que no cubre. No obstante, se sigue imprimiendo y es considerado un clásico: en un estudio de 2006, el motor de búsqueda CiteSeer listó este libro como el más citado en la literatura de ciencias de la computación.[2]
Referencias
editar- ↑ Juris Hartmanis (1982). «Computers and Intractability: A Guide to the Theory of NP-Completeness, book review». SIAM Review (en inglés) 24 (1): 90-91. Consultado el 3 de julio de 2008.
- ↑ «Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)». Consultado el 3 de noviembre de 2007.
Datos: Q938821
