О раскраске графов в классе параллельных локальных алгоритмов

Одним из способов улучшения выполнения распределенного алгоритма является представление стратегии раскраски в алгоритм, который, как известно, является эффективным в нераспределенных алгоритмах. В статье показано, что применение некоторых эвристик последовательного алгоритма раскраски, таких как наибольшие-первые (НП), наименьшие-последние (ПН) и наибольшие-первые насыщенности (НПН), для некоторых классов графов и для частных случаев вершинной раскраски в распределенных алгоритмах дают нам оптимальную или близкую к оптимальной раскраску.