?
Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements
Ch. 7. P. 93–99.
Kiselev S., Черкашин Д. Д., / Series arXiv "math". 2019.
Добавлено: 21 октября 2019 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143–155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 2019.
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Zelenova S. A., Зеленов С. В., Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 6 P. 183–202
In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions ...
Добавлено: 11 августа 2018 г.
Cherkashin Danila, Kulikov A., Andrei Raigorodskii, Discrete Applied Mathematics 2018 Vol. 243 P. 125–131
Добавлено: 6 августа 2018 г.
Зеленов С. В., Зеленова С. А., Программирование 2018 Т. 44 № 3 С. 3–16
В работе предлагается новый взгляд на проблему построения планировщика в случае группы строго периодических задач. Рассматривается представление структуры системы периодов в терминах теории графов. Дан критерий существования бесконфликтного расписания, основанный на данном представлении, а также общие схемы алгоритмов построения такого расписания. Приведены примеры применения методики для решения различных проблем, возникающих при построении расписаний для систем ...
Добавлено: 15 марта 2018 г.
Зеленова С. А., Зеленов С. В., Труды Института системного программирования РАН 2017 Т. 29 № 6 С. 183–202
В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов ...
Добавлено: 12 февраля 2018 г.
Уткина И. Е., , in: Computational Aspects and Applications in Large-Scale Networks. Springer Proceedings in Mathematics & StatisticsVol. 247.: Springer, 2018. P. 121–131.
In this article we use the modular decomposition technique for exact solving the weighted maximum clique problem. Our algorithm takes the modular decomposition tree from the paper of Tedder et. al. and finds solution recursively. Also, we propose algorithms to construct graphs with modules. We show some interesting results, comparing our solution with Ostergards algorithm ...
Добавлено: 18 октября 2017 г.
Уткина И. Е., /. 2017.
Добавлено: 15 октября 2017 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 98–104
В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...
Добавлено: 23 августа 2017 г.
Шабанов Д. А., Доклады Академии наук 2017 Т. 475 № 1 С. 24–28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Добавлено: 19 июля 2017 г.
Шитов Я. Н., Theoretical Computer Science 2017 Vol. 671 P. 116–118
Добавлено: 15 марта 2017 г.
А. И. Николаев, Информационные технологии 2016 Т. 22 № 4 С. 249–254
Представлен новый подход к решению задачи о максимальной клике. Предложенный подход состоит в том, что для данного графа с помощью машинного обучения выбирается наиболее быстрый алгоритм из нескольких алгоритмов, решающих задачу о максимальной клике. После чего выбранный алгоритм применяется для решения задачи о максимальной клике в этом графе. Вычислительные эксперименты на графах библиотеки DIMACS показывают, ...
Добавлено: 27 мая 2016 г.
Шабанов Д. А., Хузиева А. Э., Дискретная математика 2015 Т. 27 № 2 С. 112–133
В работе исследуется экстремальная проблема комбинаторного анализа об отыскании минимально возможного количества ребер в $n$-однородном гиперграфе с хроматическим числом больше $r$ и обхватом больше $s$. Получена новая нижняя оценка подобной экстремальной величины, а также ряд смежных результатов. ...
Добавлено: 23 февраля 2016 г.
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.
Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even ...
Добавлено: 24 августа 2015 г.
Комоско Л. Ф., Бацын М. В., Информационные технологии 2015 № 7 С. 488–494
В статье представлен новый эффективный эвристический алгоритм для решения задачи о раскраске графа. Предложенный алгоритм строит ту же раскраску графа, что и широко используемый жадный последовательный алгоритм раскраски, в котором на каждом шаге текущая вершина красится в минимальный допустимый цвет. Вычислительные эксперименты показывают, что представленный алгоритм выполняет раскраску графа гораздо быстрее по сравнению со стандартным ...
Добавлено: 13 июля 2015 г.
Larisa Komosko, Mikhail Batsyn, Pablo San Segundo . и др., Journal of Combinatorial Optimization 2016 No. 4 P. 1665–1677
Добавлено: 13 июля 2015 г.
Добавлено: 13 июля 2015 г.