Евстигнеев Владимир Анатольевич – д-р физ.-мат. наук, профессор, главный научный сотрудник Института систем информатики им. А.П. Ершова СО РАН г. Новосибирск, e-mail: eva@iis.nsk.su
Турсунбай кызы Ырысгуль – стажер Института систем информатики им. А.П. Ершова СО РАН г. Новосибирск, тел.: (383)330-40-47, e-mail: rtursun@yandex.ru
АНАЛИЗ ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ РАСКРАСКИ ГРАФОВ, ИСПОЛЬЗУЮЩИХ СТРАТЕГИЮ ЖАДНОГО АЛГОРИТМА
Рассматривается один из способов улучшения выполнения локального алгоритма – представление стратегии раскраски в алгоритм, который является эффективным в нераспределенных алгоритмах. Показано, что применение некоторых эвристик последовательного алгоритма раскраски, таких, как наибольшие-первые (НП), наименьшие-последние (ПН) и наибольшие-первые насыщенности (НПН), для некоторых классов графов и для частных случаев вершинной раскраски в локальных алгоритмах дают оптимальную или почти оптимальную раскраску.
Keywords in Russian:раскраска графов; распределенный алгоритм; локальный алгоритм; жадный алгоритм; w-совершенные графы; T-раскраска; суммирующая раскраска
АНАЛИЗ ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ РАСКРАСКИ ГРАФОВ, ИСПОЛЬЗУЮЩИХ СТРАТЕГИЮ ЖАДНОГО АЛГОРИТМА
Рассматривается один из способов улучшения выполнения локального алгоритма – представление стратегии раскраски в алгоритм, который является эффективным в нераспределенных алгоритмах. Показано, что применение некоторых эвристик последовательного алгоритма раскраски, таких, как наибольшие-первые (НП), наименьшие-последние (ПН) и наибольшие-первые насыщенности (НПН), для некоторых классов графов и для частных случаев вершинной раскраски в локальных алгоритмах дают оптимальную или почти оптимальную раскраску.
Keywords in Kyrgyz:раскраска графов; распределенный алгоритм; локальный алгоритм; жадный алгоритм; w-совершенные графы; T-раскраска; суммирующая раскраска
АНАЛИЗ ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ РАСКРАСКИ ГРАФОВ, ИСПОЛЬЗУЮЩИХ СТРАТЕГИЮ ЖАДНОГО АЛГОРИТМА
Рассматривается один из способов улучшения выполнения локального алгоритма – представление стратегии раскраски в алгоритм, который является эффективным в нераспределенных алгоритмах. Показано, что применение некоторых эвристик последовательного алгоритма раскраски, таких, как наибольшие-первые (НП), наименьшие-последние (ПН) и наибольшие-первые насыщенности (НПН), для некоторых классов графов и для частных случаев вершинной раскраски в локальных алгоритмах дают оптимальную или почти оптимальную раскраску.
Keywords in English:раскраска графов; распределенный алгоритм; локальный алгоритм; жадный алгоритм; w-совершенные графы; T-раскраска; суммирующая раскраска