Аннотация

Аннотация: К задаче раскраски графа можно свести различные задачи планирования и размещения ресурсов. В частности, раскраска графов используется в области высокоуровневого синтеза цифровых схем. Точное решение для раскраски графа не всегда практически достижимо. По этой причине интерес представляют эвристические алгоритмы раскраски графа, позволяющие получить допустимое решение с полиноминальной вычислительной сложностью. Такие алгоритмы могут использоваться, в частности, в задаче быстрого поиска в пространстве архитектурных вариантов при высокоуровневом синтезе вычислительной системы. В этой связи интерес представляет семейство эвристических алгоритмов ЕршоваКожухина, о котором до сих пор отсутствовали упоминания в современной литературе по анализу алгоритмов раскраски графа. В статье приводится краткое описание и псевдокод алгоритмов Ершова-Кожухина, а также приводится их экспериментальная оценка в сравнении с алгоритмами Welsh-Powell, RLF и DSATUR. Полученная оценка свидетельствует о том, что алгоритмы Ершова-Кожухина имеют преимущество в качестве формируемых решений по сравнению с популярными эвристическими алгоритмами раскраски графа.