Авторы: Ы. Турсунбай-кызы

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

Год: 2010, Номер: 6, Страницы: 105-112

Отрасль знаний: Прикладная математика

Индекс УДК: 519.174.7, 004.75

DOI: -

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

Ключевые слова: раскраска графов распределенный алгоритм локальный алгоритм жадный алгоритм совершенные графы T-раскраска суммирующая раскраска

ЦИТИРОВАНИЕ СКАЧАТЬ