Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии | Sciact - Система учета научной деятельности ИМ СО РАН

Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии Научная публикация

Журнал

Дискретный анализ и исследование операций
ISSN: 1560-7542

Вых. Данные

Год: 2026, Том: 33, Номер: 2, Страницы: 115-135 Страниц : 22 DOI: 10.33048/daio.2026.33.863

Ключевые слова

вечное вершинное покрытие, защита рёбер графа, алгоритм проверки устойчивости, динамическая игра Штакельберга.

Авторы

Утюпин С.Ю. ¹

Организации

1	Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Информация о финансировании (1)

Министерство науки и высшего образования РФ

FWNF-2026-0021

Задача о вечном вершинном покрытии является вариантом задачи о вершинном покрытии графа и может рассматриваться как динамическая игра двух сторон (атакующего и защитника) с бесконечным числом шагов. Для построения стратегии защитника задача представляется в виде динамической игры, на каждом шаге которой взаимодействие противоборствующих сторон формализуется как двухуровневая задача математического программирования. В данной работе предложена процедура, позволяющая ответить на вопрос, является ли заданное вершинное покрытие вечным. Идея процедуры заключается в рекурсивной проверке устойчивости вершинных покрытий, полученных в результате решения задач защитника и построения дополнительного графа покрытий и переходов.

Утюпин С.Ю.
Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии
Дискретный анализ и исследование операций. 2026. Т.33. №2. С.115-135. DOI: 10.33048/daio.2026.33.863

Поступила в редакцию:	8 апр. 2026 г.
Принята к публикации:	22 мая 2026 г.
Опубликована в печати:	1 окт. 2026 г.
Опубликована online:	1 окт. 2026 г.

Нет идентификаторов