?
Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements
Ch. 7. P. 93-99.
Добавлено: 13 июля 2015 г.
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 г.
Зеленов С. В., Зеленова С. А., Программирование 2018 Т. 44 № 3 С. 3-16
В работе предлагается новый взгляд на проблему построения планировщика в случае группы строго периодических задач. Рассматривается представление структуры системы периодов в терминах теории графов. Дан критерий существования бесконфликтного расписания, основанный на данном представлении, а также общие схемы алгоритмов построения такого расписания. Приведены примеры применения методики для решения различных проблем, возникающих при построении расписаний для систем ...
Добавлено: 15 марта 2018 г.
А. И. Николаев, Информационные технологии 2016 Т. 22 № 4 С. 249-254
Представлен новый подход к решению задачи о максимальной клике. Предложенный подход состоит в том, что для данного графа с помощью машинного обучения выбирается наиболее быстрый алгоритм из нескольких алгоритмов, решающих задачу о максимальной клике. После чего выбранный алгоритм применяется для решения задачи о максимальной клике в этом графе. Вычислительные эксперименты на графах библиотеки DIMACS показывают, ...
Добавлено: 27 мая 2016 г.
Скопенков М. Б., Mathematical Physics Analysis and Geometry 2022 Vol. 25 Article 18
Добавлено: 12 августа 2022 г.
Mikhail Batsyn, Boris Goldengorin, Evgeny Maslov и др., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 397-416
In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast ...
Добавлено: 17 февраля 2013 г.
Авдошин С. М., Набебин А. А., М. : ДМК Пресс, 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 г.
Зеленова С. А., Зеленов С. В., Труды Института системного программирования РАН 2017 Т. 29 № 6 С. 183-202
В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов ...
Добавлено: 12 февраля 2018 г.
Шабанов Д. А., Хузиева А. Э., Дискретная математика 2015 Т. 27 № 2 С. 112-133
В работе исследуется экстремальная проблема комбинаторного анализа об отыскании минимально возможного количества ребер в $n$-однородном гиперграфе с хроматическим числом больше $r$ и обхватом больше $s$. Получена новая нижняя оценка подобной экстремальной величины, а также ряд смежных результатов. ...
Добавлено: 23 февраля 2016 г.
Шитов Я. Н., Theoretical Computer Science 2017 Vol. 671 P. 116-118
Добавлено: 15 марта 2017 г.
Cherkashin Danila, Kulikov A., Andrei Raigorodskii, Discrete Applied Mathematics 2018 Vol. 243 P. 125-131
Добавлено: 6 августа 2018 г.
Уткина И. Е., / Cornell University Library. 2017.
Добавлено: 15 октября 2017 г.
Шабанов Д. А., Доклады Академии наук 2017 Т. 475 № 1 С. 24-28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Добавлено: 19 июля 2017 г.
Larisa Komosko, Mikhail Batsyn, Pablo San Segundo . и др., Journal of Combinatorial Optimization 2016 No. 4 P. 1665-1677
Добавлено: 13 июля 2015 г.
Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, Journal of Global Optimization 2014 Vol. 59 No. 1 P. 1-21
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed ...
Добавлено: 24 мая 2013 г.
Kiselev S., Черкашин Д. Д., / Cornell University. Series arXiv "math". 2019.
Добавлено: 21 октября 2019 г.
Калягин В. А., Колданов А. П., Koldanov P.A. и др., Computational Management Science 2013 Vol. 10 No. 2-3 P. 105-124
Добавлено: 3 апреля 2013 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 98-104
В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...
Добавлено: 23 августа 2017 г.
Малышев Д. С., Пардалос П. О., Optimization Letters 2015 Vol. 9 No. 5 P. 839-843
The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure
of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss ...
Добавлено: 26 сентября 2014 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
Уткина И. Е., , in : Computational Aspects and Applications in Large-Scale Networks. Springer Proceedings in Mathematics & Statistics. Vol. 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 г.