Approximation algorithms for double domination number of graphs

doi:10.17223/20710410/72/6

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Approximation algorithms for double domination number of graphs	633 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/72/6

#доминирующее множество

#число 2-доминирования

#сложность алгоритма

#аппроксимационный алгоритм

Title: Approximation algorithms for double domination number of graphs
Title: Приближенные алгоритмы для числа 2-доминирования графов
Creator: Magima, M.
|
Ragukumar, P.
Date: 2026
DOI: 10.17223/20710410/72/6
Description: Для k ∈ N k-кортежное доминирующее множество графа G = (V, Е) - это под множество D ⊆ V, такое, что каждая вершина в графе имеет по меньшей мере k соседей в множестве D. k-Кортежное доминирующее число уkх (G) - минимальный размер множества графа G. Частный случай, когда k = 1, является обычным доминирующим. Случай, когда к = 2, называется двойным доминирующим или 2-кортежным доминирующим. Минимальная мощность двойного доминирующего множества, обозначаемая y2x (G), - это число 2-доминирования графа G. Известно, что нахождение минимального двойного доминирующего множества графа является NP-полной задачей и остаётся таковой для специальных классов графов, включая двудольные. В данной работе проблема двойного доминирования рассматривается с алгоритмической точки зрения. Представлен эффективный аппроксимационный алгоритм нахождения множества двойного доминирования двудольного графа с использованием покрытия вершин и его адаптация для любого связного графа.