Computers and Intractability: A Guide to the Theory of NP-Completeness

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Computers and Intractability: A Guide to the Theory of NP-Completeness
Autor Michael Garey y David S. Johnson
Género Libro de texto
Tema(s) Ciencias de la computación
Idioma inglés
Editorial W.H. Freeman y Cía.
Fecha de publicación 1979
Formato Impreso
ISBN 0-7167-1045-5
OCLC OCLC 247570676

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.

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]