?
Представления ребер гиперграфов обобщенными путями
Дискретный анализ и исследование операций. 2023. Т. 30. № 3(157). С. 81–95.
Вялый М. Н., Карпов В. Е.
Изучается задача реализации гиперграфа на графе с условием, что каждое ребро гиперграфа реализуется подграфом, в котором ровно две вершины имеют нечётную степень. Установлена связь такой задачи реализации гиперграфов и гипотезы о двойном покрытии циклами. Доказана алгоритмическая трудность проверки существования реализации в различных постановках: реализации на всех графах, на простых графах и на графах из нескольких очень узких классов.
Ключевые слова: гиперграфNP-полнотаEulerian graphs hypergraphcycle cover NP-completenessпокрытие цикламиэйлеров граф
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Медведев В. О., Annals of Global Analysis and Geometry 2026 Vol. 70 No. 2 P. 8–23
Добавлено: 19 сентября 2026 г.
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 323–334
Добавлено: 19 сентября 2026 г.
Aleksei Samarin, Назаренко А. А., Kotenko E. и др., Proceedings of the ACM on Management of Data, USA 2026 Vol. 4 No. 1 P. 1–28
Добавлено: 19 сентября 2026 г.
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2025 Vol. 35 No. 2 P. 148–158
Добавлено: 19 сентября 2026 г.
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 302–312
Добавлено: 19 сентября 2026 г.
Springer, Cham, 2026.
Добавлено: 19 сентября 2026 г.
Springer, Cham, 2026.
Добавлено: 19 сентября 2026 г.
FRUCT Oy, 2024.
Добавлено: 19 сентября 2026 г.
FRUCT Oy, 2024.
Добавлено: 19 сентября 2026 г.
FRUCT Oy, 2025.
Добавлено: 19 сентября 2026 г.
FRUCT Oy, 2026.
Добавлено: 19 сентября 2026 г.
Aleksei Samarin, Назаренко А. А., Kotenko E. и др., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 8 P. 1–26
Добавлено: 19 сентября 2026 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
M. N. Vyalyi, Karpov V. E., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 3 P. 678–686
Добавлено: 30 ноября 2023 г.
Добавлено: 12 ноября 2023 г.
Добавлено: 28 июля 2023 г.
Дугинов О. И., Кускова Б. М., Малышев Д. С. и др., Труды института математики и механики УрО РАН 2022 Т. 28 № 2 С. 114–142
Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально, если оно не содержится ни в каком другом диссоциирующем множестве с бо́льшим числом вершин. В данной работе предлагаются оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Доказано, что задача нахождения максимального диссоциирующего множества наибольшей мощности ...
Добавлено: 19 сентября 2022 г.
Balobanov A., Шабанов Д. А., Discrete Mathematics 2021 Vol. 344 No. 3 Article 112231
Добавлено: 27 ноября 2020 г.
Шабанов Д. А., Шайхеева Т. М., Математические заметки 2020 Т. 107 № 3 С. 454–465
Работа посвящена предписанным раскраскам однородных гиперграфов. Пусть H(m,r,k) - это полный r-дольный k-однородный гиперграф с равными размерами долей $m$, в котором каждое ребро содержит ровно по одной вершине из некоторых k<= r долей. С помощью результатов о кратных покрытиях независимыми множествами найдена асимптотика предписанного хроматического числа H(m,r,k) с ростом m для фиксированных k и r. ...
Добавлено: 14 июня 2020 г.
Работа посвящена изучению пороговой вероятности наличия полноцветной раскраски в r цветов у случайного k-однородного гиперграфа в биномиальной модели H(n,k,p), т.е. такой раскраски, что каждое ребро гиперграфа содержит вершины всех r цветов. Показано, что данная пороговая вероятность при фиксированных r<k и растущем n отвечает разреженному случаю, т.е. случаю линейного среднего числа ребер cn для положительного фиксированного ...
Добавлено: 5 июня 2019 г.
Клемашев Н. И., Шананин А. А., Труды Московского физико-технического института 2015 Т. 7 № 4 С. 17–27
Доказана NP-полнота непараметрического теста для модели временного диктатора с несколькими диктаторами с положительно-однородными функциями полезности. ...
Добавлено: 5 марта 2019 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 2019.
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Шабанов Д. А., Kupavskii A., Combinatorics Probability and Computing 2018 Vol. 27 No. 2 P. 245–273
Добавлено: 22 февраля 2018 г.
Шабанов Д. А., Балобанов А. Е., Математические заметки 2018 Т. 103 № 1 С. 38–48
В работе исследуются экстремальные задачи о числе j-независимых множеств в однородных простых гиперграфах. Получены близкие к оптимальным результаты для максимального количества независимых множеств в классе простых регулярных гиперграфов, а также для минимального числа - в классе простых гиперграфов с заданной средней степенью вершины. ...
Добавлено: 13 февраля 2018 г.