Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи

Монография. — М.: Мир, 1982. — 420 с.Монография американских ученых посвящена решению сложных (в том числе и NP-трудных) комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории автоматов с примерами.Вычислительные машины, сложность и труднорешаемые задачи.
Теория NP-полных задач.
Доказательство результатов об NP-полноте.
Применение теории NP-полноты для анализа задач.
NP-трудные задачи.
Подходы к решению NP-полных задач.
За пределами класса NP-полных задач.
Приложение. Список NP-полных задач.
Теория графов.
Построение сетей.
Множества и разбиения.
Хранение и поиск данных.
Задачи теории расписаний.
Математическое программирование.
Игры и головоломки.
Логика.
Теория автоматов и языков.
Оптимизация программ.
Разное.
Открытые задачи.