Обзор литературы показывает, что все известные точные алгоритмы раскраски чрезвычайно трудоемки и позволяют раскрашивать лишь ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Алексеев А.С. Исследования по прикладной теории графов


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

(cкачать страницу)

Смотреть книгу на libgen

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