Version maximale de la couverture de l'ensemble dominant

Question

Le problème de l'ensemble dominant est:

donné un $ N $ graphe vertex $ g= (v, e) $ , trouver un régler s (\ sous -éréeq v) $ tel que $ | n [s] | $ est exactement < SPAN CLASS="MATH-CONTENANT"> N $ N $ , où $$ N [S]:={x ~ | \ Text {$ x $ $ ou un voisin de $ x $ réside en $ s $} \} $$

Ma question est si ce qui suit (nouveau problème) a un nom défini dans la littérature, et sinon ce qui devrait être le nom le plus approprié.

Nouveau problème: donné à un $ n $ graphe vertex $ g= (v, E) $ et un entier $ k $ , trouver un ensemble s (\ sous -éréq v) $ < / span> de taille $ k $ tel que $ | n [s] | $ est maximisé. < / p>

Pour le deuxième problème, certains des noms que j'ai vus dans la littérature sont une couverture maximale graphique; couverture partielle; K-Dominating-Set, (Toutefois, les mêmes noms sont également utilisés dans d'autres contextes).

Answer 1

Le problème dans lequel vous devez sélectionner $ K $ Les sommets pour maximiser le nombre de sommets dominés sont connus sous le nom de problème de fixation dominant budgété . Le problème ou sa variante connectée est étudié au moins par Lamprou, Sigalis et Zissimoprochos [1] et Khuller, Purohit et Sarpatwar [2]. Il apparaît également dans l'enquête récente de Narayanaswamy et de Vijayaragunathan [3].

---

[1] Lamprou, ioannis, Ioannis Sigalas et Vassilis Zissimopoulos. "Amélioration de la domination de la domination et du budget budgétisé-Vertex." Preprint ARXIV Arxiv: 1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit et Kanthi K. Sarpatwar. "Analyse du voisinage optimal: algorithmes pour les problèmes définis budgétisés et partiels connectés." Actes de la vingt-cinquième symposium annuel ACM-Siam sur des algorithmes discrètes. Société pour les mathématiques industrielles et appliquées, 2014.

[3] Narayanaswamy, N. S. et R. Vijayaragunathan. "Optimisation paramétrée dans des graphiques incertains - une enquête et des résultats." Algorithmes 13.1 (2020): 3.