Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретный анализ и исследование операций, 2023, том 30, выпуск 3, страницы 81–95
DOI: https://doi.org/10.33048/daio.2023.30.757 (Mi da1328) 		 
Представления рёбер гиперграфов обобщёнными путями

М. Н. Вялыйabc, В. Е. Карповa

a Московский физико-технический институт (гос. университет), Институтский пер., 9, 141701 Долгопрудный, Россия
b Федеральный исследовательский центр «Информатика и управление» РАН, ул. Вавилова, 42, 119333 Москва, Россия
c Национальный исследовательский университет «Высшая школа экономики», Покровский б-р, 11, 109028 Москва, Россия
PDF полного текста (337 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.33048/daio.2023.30.757
Аннотация: Изучается задача реализации гиперграфа на графе с условием, что каждое ребро гиперграфа реализуется подграфом, в котором ровно две вершины имеют нечётную степень. Установлена связь такой задачи реализации гиперграфов и гипотезы о двойном покрытии циклами. Доказана алгоритмическая трудность проверки существования реализации в различных постановках: реализации на всех графах, на простых графах и на графах из нескольких очень узких классов. Библиогр. 11.
Ключевые слова: гиперграф, покрытие циклами, эйлеров граф, NP-полнота.
Финансовая поддержка Номер гранта
Программа фундаментальных исследований НИУ ВШЭ 0063--2019--0003
Работа первого автора выполнена при поддержке Программы фундаментальных исследований НИУ ВШЭ, а также в рамках государственного задания ФИЦ ИУ РАН (проект № 0063–2019–0003).
Статья поступила: 21.11.2022
Переработанный вариант: 27.02.2023
Принята к публикации: 03.03.2023
Тип публикации: Статья
УДК: 519.171
Образец цитирования: М. Н. Вялый, В. Е. Карпов, “Представления рёбер гиперграфов обобщёнными путями”, Дискретн. анализ и исслед. опер., 30:3 (2023), 81–95
Цитирование в формате AMSBIB
\RBibitem{VyaKar23}
\by М.~Н.~Вялый, В.~Е.~Карпов
\paper Представления рёбер гиперграфов обобщёнными~путями
\jour Дискретн. анализ и исслед. опер.
\yr 2023
\vol 30
\issue 3
\pages 81--95
\mathnet{http://mi.mathnet.ru/da1328}
\crossref{https://doi.org/10.33048/daio.2023.30.757}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da1328
  • https://www.mathnet.ru/rus/da/v30/i3/p81
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024