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

Библиографическая ссылка: Береснев В.Л. , Мельников А.А. , Утюпин С.Ю.
Устойчивость вершинных покрытий в игре с конечным числом шагов
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.28–45. DOI: 10.33048/daio.2024.31.797 РИНЦ

Переводная: Beresnev V.L. , Melnikov A.A. , Utyupin S.Y.
Stability of Vertex Covers in a Game with Finitely Many Steps
Journal of Applied and Industrial Mathematics. 2024. V.18. N2. P.206-215. DOI: 10.1134/s1990478924020030 Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	26 февр. 2024 г.
Принята к публикации:	21 мар. 2024 г.
Опубликована в печати:	8 авг. 2024 г.
Опубликована online:	8 авг. 2024 г.

Идентификаторы БД:

РИНЦ:

68484577

Цитирование в БД: Пока нет цитирований

Альметрики: