14.7. Замечания, касающиеся литературы

Различные графовые и комбинаторные алгоритмы описаны в работах [14. 40, 14.47-14.53]. Обсуждение методов представления графов имеется в работах [14.40, 14.41].

Время выполнения алгоритмов, описанных в этой книге, ограничено сверху некоторым полиномом от числа вершин и числа ребер графа. Пусть 53 — класс всех проблем, которые можно решить алгоритмами с полиномиальной сложностью. Существует большое число проблем, для которых не известно, существуют ли алгоритмы с полиномиальным временем решения. Многие из них можно решить за полиномиальное время недетерминированными алгоритмами. Класс таких проблем обозначается через Проблема является -трудной, если детерминированный алгоритм с полиномиальной сложностью для ее решения можно использовать для поиска детерминированного алгоритма с полиномиальной сложностью для решения любой проблемы из 9753 — трудная проблема из называется -полной. Таким образом, если детерминированный алгоритм с полиномиальной сложностью для какой-либо проблемы из класса -полных существует, то такой алгоритм существует для каждой проблемы в 915. В основополагающей работе [14.54] показано, что проблема выполнимости -полна. В работе [14.55] демонстрируется -полнота большого класса проблем, работах [14.56, 14.57] дается элегантное введение в теорию -полноты и доказывается -полнота нескольких графовых проблем. Упоминания об этом имеются также в работах [14.40, 14.51, 14.57]. В указанных работах имеются сообщения о многих интересных графовых алгоритмах. Некоторые из них перечислены в конце следующей главы.