Обзор литературы показывает, что все известные точные алгоритмы раскраски чрезвычайно трудоемки и позволяют раскрашивать лишь ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Алексеев А.С.
Исследования по прикладной теории графов
Обзор литературы показывает, что все известные точные алгоритмы раскраски чрезвычайно трудоемки и позволяют раскрашивать лишь графы с числом вершин в пределах сотни, что явно недостаточно для решения реальных задач логического проектирования дискретных устройств. Трудности, препятствующие существенному повышению размерности точно решаемых задач, носят принципиальный характер: задача раскраски вершин графа является ЛФ-трудной. Поэтому для решения практических задач обычно приходится использовать приближенные алгоритмы раскраски. В работе [17] приведены результаты исследования известных и предлагаемых приближенных алгоритмов раскраски, позволившие выявить наиболее эффективные алгоритмы и области их предпочтительного использования.