• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Быстрый алгоритм для решения задачи о раскраске графа с использованием битовых операций

С. 432-438.
Комоско Л.Ф., Бацын М.В.

В статье рассматривается задача о раскраске графа. Предложен эвристический алгоритм, позволяющий получить раскраску графа (вектор из n натуральных чисел) с помощью математических операций над битовым представлением матрицы смежности графа. Скорость и точность данного алгоритма сравнивается с этими же характеристиками известного алгоритма GIS (Greedy Independent Sets-Colour). Результаты сравнения двух алгоритмов, выполнены на графах библиотеки DIMACS. Они показывают, что предложенный эвристический алгоритм выполняет раскраску графа быстрее по сравнению со стандартным подходом к его реализации.