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

Комоско Л.Ф.; Бацын М.В.

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

Новости

3 июля 2026 г.

Исследование НИУ ВШЭ: молодые россияне едут в крупные города за высшим образованием

За период с 2011 по 2021 год число переездов 18-летних россиян составило 1,2 млн человек. Из них 78% отправились в 160 крупных городов, что с большой долей вероятности связано с желанием получить высшее образование. Лидеры по формированию вузовских зон притяжения: Москва, Санкт-Петербург, Екатеринбург, Ростов-на-Дону, Краснодар, Новосибирск.

2 июля 2026 г.

Ученые НИУ ВШЭ в Санкт-Петербурге создали микролазер размером с бактерию

Международная команда исследователей при участии НИУ ВШЭ в Санкт-Петербурге создала микролазеры, излучающие в диапазоне глубокого ультрафиолета — 255 нанометров. Устройства работают при комнатной температуре, а диаметр самого маленького из них — около двух микрометров, что сопоставимо с размером бактерии. Такие лазеры могут применяться для сенсоров, спектроскопических систем, фотонных чипов и устройств связи. Работа опубликована в журнале Optics & Laser Technology.

1 июля 2026 г.

Ученые НИУ ВШЭ выяснили, кто и почему в России питается вне дома

Около трети населения (31,3%) практически не едят вне дома и не покупают готовую еду. Ядро активных потребителей — тех, кто питается вне дома или покупает готовое почти ежедневно или несколько раз в неделю, — составляет всего около 9%. Таковы результаты исследования, проведенного Институтом социальной политики НИУ ВШЭ. Как отмечают авторы, питание вне дома в России перестало быть маркером высокого статуса.

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации

?

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

С. 432–438.

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

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

Язык: русский

Полный текст

Текст на другом сайте

Ключевые слова: bitwise operations graph colouring problem битовые операции задача о раскраске графа

В книге

Труды 38-й конференции "Информационные технологии и системы - 2014"

Н. Новгород: ИППИ РАН, 2014.

Теоремы существования и достаточности, связанные с локальными преобразованиями графов для задачи о k-раскраске

Сироткин Д. В., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 98–104

В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...

Добавлено: 23 августа 2017 г.

Эффективная раскраска графа с помощью битовых операций

Комоско Л. Ф., Бацын М. В., Информационные технологии 2015 № 7 С. 488–494

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

Добавлено: 13 июля 2015 г.

A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations

Larisa Komosko, Mikhail Batsyn, Pablo San Segundo . и др., Journal of Combinatorial Optimization 2016 No. 4 P. 1665–1677

Добавлено: 13 июля 2015 г.