?
A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length
Theoretical Computer Science. 2017. Vol. 671. P. 116–118.
Шитов Я. Н.
Ключевые слова: graph coloring
Болбачан В. С., / Series math "arxiv.org". 2024.
Полилогарифмы Чжоу — это специальные функции, возникающие при явном описании отображения регулятора Бейлинсона. Наиболее интересное функциональное уравнение для этой функции отражает тот факт, что она обращается в нуль на границе в комплексе циклов Блоха. Мы показываем, что это функциональное уравнение формально вытекает из более простых свойств: кососимметричности, функториальности и мультипликативности. Для доказательства этого мы рассматриваем ...
Добавлено: 16 июля 2026 г.
Болбачан В. С., / Series math "arxiv.org". 2024.
Пусть K поле характеристики ноль. Мы доказываем что его когомологии в степени m-1 и весе m рационально изоморфны когомологиям полилогарифмического комплекса в соответствующей степени. Это дает частичное расширение теоремы Суслина, описывающую неразложимую K теорию K_3 для поля. ...
Добавлено: 16 июля 2026 г.
Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.
Добавлено: 9 июля 2026 г.
Добавлено: 11 июня 2026 г.
Медведев В. О., / Series arXiv "math". 2026.
We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...
Добавлено: 3 апреля 2026 г.
Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.
Добавлено: 2 апреля 2026 г.
Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...
Добавлено: 15 января 2026 г.
Гаянов Н. В., Парусникова А. В., / Cornell University. Серия math "arxiv.org". 2025.
Рассматривается алгебраическое q-разностное уравнение. Предлагается достаточное условие существования формального степенно- логарифмического разложения решения такого уравнения в окрест- ности нуля. Приводится пример применения этого достаточного условия для построения формального разложения решения неко- торого q-разностного аналога пятого уравнения Пенлеве при конкретных значениях параметров уравнения; рассматриваются два различных значения числа q, приводящие к качественно разным формальным асимптотическим разложениям ...
Добавлено: 25 декабря 2025 г.
Гнетов Ф. А., Конаков В. Д., / Series arXiv "math". 2025. No. 2512.04667.
Добавлено: 5 декабря 2025 г.
Добавлено: 4 декабря 2025 г.
Kiselev S., Черкашин Д. Д., / Series arXiv "math". 2019.
Добавлено: 21 октября 2019 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 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 Т. 19 № 2 С. 98–104
В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...
Добавлено: 23 августа 2017 г.
Комоско Л. Ф., Бацын М. В., Информационные технологии 2015 № 7 С. 488–494
В статье представлен новый эффективный эвристический алгоритм для решения задачи о раскраске графа. Предложенный алгоритм строит ту же раскраску графа, что и широко используемый жадный последовательный алгоритм раскраски, в котором на каждом шаге текущая вершина красится в минимальный допустимый цвет. Вычислительные эксперименты показывают, что представленный алгоритм выполняет раскраску графа гораздо быстрее по сравнению со стандартным ...
Добавлено: 13 июля 2015 г.