?
Using modular decomposition technique to solve the maximum clique problem
Cornell University Library
,
2017.
Уткина И. Е.
Научное направление:
Компьютерные науки
Приоритетные направления:
компьютерно-математическое
Язык:
английский
Уткина И. Е., , 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 г.
МГУ, МАКС Пресс, 2018
В сборнике представлены труды десятой международной конференции «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 23–25 мая 2018 г.). Тематика конференции включает следующие направления: дискретные функциональные системы, свойства дискретных функций, синтез и сложность управляющих систем, надежность, контроль и диагностика управляющих систем, автоматы, теория графов, комбинаторика, теория кодирования, математические методы защиты информации, теория распознавания образов, ...
Добавлено: 14 июня 2018 г.
Рябинин К. В., Белоусов К. И., Чуприна С. И. и др., Научная визуализация 2018 Т. 10 № 4 С. 82-99
Статья посвящена вопросам применения методов и средств визуальной аналитики для систематизации результатов многопараметрического описания пользователей социальных интернет-сервисов. В данной статье под многопараметрическим описанием понимается описание языковых характеристик письменной речи пользователей социальных интернет-сервисов, извлекаемых из написанных ими комментариев и сообщений, а также психологические и социальные характеристики, извлекаемые из указанных в их профилях сведений, и из результатов ...
Добавлено: 13 ноября 2018 г.
Springer, 2017
This book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017.
The 31 full papers presented in this volume were carefully reviewed and selected
from 71 submissions. They cover a wide range of areas, aiming at connecting theory and applications ...
Добавлено: 12 июля 2019 г.
Омельченко А. В., М. : МЦНМО, 2018
В основу данного учебника легли материалы семестрового курса лекций, читающегося автором в течение нескольких лет студентам первых курсов бакалавриата Санкт-Петербургского Академического университета. В учебник включены все основные разделы современной теории графов-деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы. В конце каждого параграфа приводятся задачи, дополняющие изложенный в учебнике теоретический материал. Все утверждения снабжены ...
Добавлено: 29 августа 2018 г.
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 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
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 г.
Малышев Д. С., Пардалос П. О., 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 г.
А. И. Николаев, Информационные технологии 2016 Т. 22 № 4 С. 249-254
Представлен новый подход к решению задачи о максимальной клике. Предложенный подход состоит в том, что для данного графа с помощью машинного обучения выбирается наиболее быстрый алгоритм из нескольких алгоритмов, решающих задачу о максимальной клике. После чего выбранный алгоритм применяется для решения задачи о максимальной клике в этом графе. Вычислительные эксперименты на графах библиотеки DIMACS показывают, ...
Добавлено: 27 мая 2016 г.
Цуканова О. А., Мальцева С. В., Автоматизация и современные технологии 2013 № 11 С. 26-29
Сформулирован и обоснован концептуальный подход к созданию методики формирования управляемого информационного пространства состояний сетевого сообщества с помощью моделирования условно текстурированной ресурсной среды на основе итерации структуры сетевого сообщества, отображаемого в формате единого информационного ресурса. ...
Добавлено: 13 ноября 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 г.
Pham S. K., Antipov D., Sirotkin Alexander и др., Journal of Computational Biology 2013 Vol. 20 No. 4 P. 359-371
Добавлено: 21 марта 2014 г.
Власенко Д. В., Заикин А. А., Захаров Д. Г., Известия высших учебных заведений. Прикладная нелинейная динамика 2023 Т. 31 № 5 С. 661-669
Поскольку мозг — это чрезвычайно сложная гиперсеть взаимодействующих между собой макроскопических подсетей, проведение полномасштабного анализа его активности представляется труднейшей задачей. Тем не менее эту задачу можно существенно упростить, анализируя соответствие различных паттернов макроскопической активности мозга, например, на снимках функциональной магнитно-резонансной томографии (фМРТ), выполнению тех или иных когнитивных задач или патологическим состояниям.
Цель данной работы — предложить ...
Добавлено: 4 октября 2023 г.
Авдошин С. М., Набебин А. А., М. : ДМК Пресс, 2019
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Vizgunov Arsenii, Goldengorin B., Калягин В. А. и др., Computational Management Science 2014 Vol. 11 No. 1-2 P. 45-55
We consider a market graph model of the Russian stock market. To study the peculiarity of the Russian market we construct the market graphs for different time periods from 2007 to 2011. As characteristics of constructed market graphs we use the distribution of correlations, size and structure of maximum cliques, and relationship between return and ...
Добавлено: 20 августа 2013 г.
М. : Издательский центр «Российский государственный гуманитарный университет», 2019
Сборник включает 27 докладов международной конференции по компьютерной лингвистике и интеллектуальным технологиям «Диалог 2019», не вошедшие в ежегодник «Компьютерная лингвистика и интеллектуальные технологии», но рекомендованные Программным Комитетом к представлению на конференции. Для специалистов в области теоретической и прикладной лингвистики и интеллектуальных технологий. ...
Добавлено: 10 декабря 2019 г.
Карпов В. Э., Карпова И. П., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Добавлено: 14 марта 2015 г.
Skoptsov K. A., Sheshenin S., Галатенко В. В. и др., International Journal of Applied Mechanics 2016 Vol. 8 No. 2 P. 1650016-01-1650016-18
We present a method for evaluating elastic properties of a composite material produced by molding a resin filled with short elastic fibers. A flow of the filled resin is simulated numerically using a mesh-free method. After that, assuming that spatial distribution and orientation of fibers are not significantly changed during polymerization, effective elastic moduli of ...
Добавлено: 22 мая 2016 г.
Сотникова С. Ю., Динамика сложных систем 2012 № 3 С. 84-87
В статье описывается разработанный программный комплекс моделирования физических процессов, который также позволяет проводить идентификацию параметров печатного узла (физической модели), на котором реализуется проектируемый бортовой источник вторичного электропитания. Для него разработаны интерфейсы связи управляющей программы с известными программами моделирования и оптимизации. ...
Добавлено: 5 декабря 2014 г.
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Добавлено: 18 ноября 2013 г.
В статье представлена технология, позволяющая собирать в полевых исследованиях пространственно локализованные данные об объектах городской среды. Технология основана на автоматической привязке фотографий к пространственным координатам. Приведен план полевых и камеральных мероприятий, предложены варианты ГИС-обработки собираемых таким образом данных. В качестве примера приведены данные об использовании белорусского языка в общественном пространстве городов Белоруссии. ...
Добавлено: 12 апреля 2015 г.
Chuprikov P., Николенко С. И., Davydow A. и др., IEEE Transactions on Networking 2018 Vol. 26 No. 1 P. 342-355
Добавлено: 14 марта 2018 г.
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. и др., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Добавлено: 27 января 2014 г.