Stability of Vertex Covers in a Game with Finitely Many Steps Научная публикация
| Журнал |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 18, Номер: 2, Страницы: 206-215 Страниц : 10 DOI: 10.1134/s1990478924020030 | ||||
| Ключевые слова | dynamic Stackelberg game, eternal vertex cover, graph edge protection, stability check algorithm | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
Реферат:
The eternal vertex cover problem is a version of the graph vertex cover problem that can be represented as a dynamic game between two players (the Attacker and the Defender) with an infinite number of steps. At each step, there is an arrangement of guards over the vertices of the graph forming a vertex cover. When the Attacker attacks one of the graph’s edges, the Defender must move the guard along the attacked edge from one vertex to the other. In addition, the Defender can move any number of other guards from their current vertices to some adjacent ones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertex cover after the attack. In this paper, we propose a procedure that allows us to answer the question whether there exists a winning Defender strategy that permits protecting a given vertex cover for a given finite number of steps. To construct the Defender strategy, the problem is represented as a dynamic Stackelberg game in which at each step the interaction of the opposing sides is formalized as a two-level mathematical programming problem. The idea of the procedure is to recursively check the 1-stability of vertex covers obtained as a result of solving lower-level problems and to use some information about the covers already considered.
Библиографическая ссылка:
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
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
Оригинальная:
Береснев В.Л.
, Мельников А.А.
, Утюпин С.Ю.
Устойчивость вершинных покрытий в игре с конечным числом шагов
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.28–45. DOI: 10.33048/daio.2024.31.797 РИНЦ
Устойчивость вершинных покрытий в игре с конечным числом шагов
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.28–45. DOI: 10.33048/daio.2024.31.797 РИНЦ
Даты:
| Поступила в редакцию: | 26 февр. 2024 г. |
| Принята к публикации: | 21 мар. 2024 г. |
| Опубликована в печати: | 15 авг. 2024 г. |
| Опубликована online: | 15 авг. 2024 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85201428060 |
| РИНЦ: | 68611698 |
| OpenAlex: | W4401604048 |
Цитирование в БД:
Пока нет цитирований