?
Reusing the Same Coloring in the Child Nodes of the Search Tree for the Maximum Clique Problem
Lecture Notes in Computer Science. 2015. Vol. 8994. P. 275–280.
Добавлено: 19 мая 2026 г.
Добавлено: 28 апреля 2026 г.
Добавлено: 20 апреля 2026 г.
Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.
Добавлено: 2 апреля 2026 г.
Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...
Добавлено: 15 января 2026 г.
Петрованов И. С., Сергеев А. В., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.
Добавлено: 24 декабря 2025 г.
Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset
Меньшиков И. А., Бернадотт А. К., Елфимов Н. С., / Series arXie "Statistical mechanics". 2025.
Добавлено: 1 декабря 2025 г.
Рубчинский А. А., Чубарова Д. А., / Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2025. No. WP7/2025/01.
Добавлено: 9 ноября 2025 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143–155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
Irina Utkina, Mikhail Batsyn, Ekaterina Batsyna, , in: Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings.: Springer, 2016. P. 244–255.
Добавлено: 3 октября 2018 г.
Добавлено: 30 августа 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 Т. 13 № 1 С. 19–24
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра ...
Добавлено: 26 сентября 2017 г.
Задача Структурного Сопоставления Протеинов (ЗССП) заключается в поиске наилучшего сопоставления двух протеинов, заданных их первичными структурами. В задаче определяется наиболее близкая подструктура у двух протеинов. Эта задача полиномиально сводится к Задаче о Максимальной Клике (ЗМК) в графе сопоставления. В данной работе представлен эффективный алгоритм для ЗССП, основанный на нашем алгоритме ILS&MCS (Batsyn et al., 2014) ...
Добавлено: 24 октября 2016 г.
А. И. Николаев, Информационные технологии 2016 Т. 22 № 4 С. 249–254
Представлен новый подход к решению задачи о максимальной клике. Предложенный подход состоит в том, что для данного графа с помощью машинного обучения выбирается наиболее быстрый алгоритм из нескольких алгоритмов, решающих задачу о максимальной клике. После чего выбранный алгоритм применяется для решения задачи о максимальной клике в этом графе. Вычислительные эксперименты на графах библиотеки DIMACS показывают, ...
Добавлено: 27 мая 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 г.
Малышев Д. С., Пардалос П. О., 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 г.
Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, , in: Models, Algorithms, and Technologies for Network AnalysisVol. 59.: NY: Springer, 2013. Ch. 7 P. 93–99.
Добавлено: 19 ноября 2013 г.
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 г.
Калягин В. А., Колданов А. П., Koldanov P.A. и др., Computational Management Science 2013 Vol. 10 No. 2-3 P. 105–124
Добавлено: 3 апреля 2013 г.
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 г.