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

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

АБВ
АБВ
АБВ

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

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

по году

Тематика

Новости

20 октября 2026 г.

«Наши работы можно назвать исследованиями на переднем крае науки»

Международная лаборатория кластерной геометрии, действующая на факультете математики НИУ ВШЭ, занимается формированием новой научной дисциплины, соединяющей в себе знания из различных областей математики. Выполненные в ней работы вызывают большой интерес, в том числе у зарубежных коллег. Лаборатория изучает семейства кривых и разрабатывает методы, применяемые в исследованиях физического микромира. Новостная служба «Вышка.Главное» побеседовала с заведующим лабораторией профессором Сергеем Ландо.

20 октября 2026 г.

За гранью возможного: в Вышке прошел финал IX сезона «Научных боев»

В конце сентября в Центре культур НИУ ВШЭ прошел финал IX сезона «Научных боев» с заглавной темой «За гранью возможного». Исследователи представили четыре работы. На каждое выступление отводилось по десять минут, после чего участники отвечали на вопросы жюри и зрителей. Спикеры искали границы между человеком и искусственным интеллектом, цифровой платформой и ее пользователями, государством и социальной инфраструктурой, а также между тем, как общество определяет человека, и тем, как он определяет себя сам.

15 октября 2026 г.

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

Исследователи Центра языка и мозга НИУ ВШЭ совместно с зарубежными коллегами показали, что в конце первого класса у детей уже сформирован один из важных навыков движений глаз при чтении. Они, как и взрослые, быстро адаптируют длину саккад — быстрых скачков взгляда — к длине слов в предложениях. При этом место, куда приземляется взгляд, у детей смещено к началу слова, в отличие от взрослых, которые смотрят в середину слова. Чем выше беглость чтения, тем ближе эта позиция к центру. Результаты исследования опубликованы в Journal of Experimental Child Psychology.

Нашли опечатку?
Выделите её, нажмите 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 г.