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

de Michael Garey y David S. Johnson

Género

Libro de texto

Tema(s)

Ciencias de la computación

Idioma

Inglés

Editorial
Fecha de publicación

1979

Formato

Impreso

ISBN

0-7167-1045-5

OCLC

247570676

[editar datos en Wikidata]

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]