Versión máxima de cobertura de Dominating Set
-
28-09-2020 - |
Pregunta
El problema de conjunto dominante es:
Dado un $ n $ el gráfico de vértice $ g= (v, e) $ , encuentre un Establezca $ s (\ subsetaq v) $ tal que $ | n [s] | $ es exactamente < Span Class="Math-contenedor"> $ n $ , donde $$ n [s]:={x ~ | \ Text {ya sea $ x $ o un vecino de $ x $ se encuentra en $ s $} \} $$
Mi pregunta es si el siguiente (nuevo problema) tiene un nombre definido en la literatura, y si no es lo que debería ser el nombre más apropiado.
Nuevo problema: Dado un $ n $ el gráfico de vértice $ g= (v, E) $ y un entero $ k $ , encuentre un conjunto $ s (\ subesteideq v) $ < / SPAN> de tamaño $ k $ tal que $ | n [s] | $ se maximiza. < / p>
Para el segundo problema, algunos de los nombres que he visto en la literatura son la cobertura máxima de gráficos; cobertura parcial; K-Dominating-Set, (sin embargo, los mismos nombres exactamente también se utilizan en otros contextos).
Solución
El problema en el que debe seleccionar $ k $ vértices para maximizar el número de vértices dominados se conoce como el problema del conjunto de dominación presupuestado de . El problema o su variante conectada se estudia al menos por Lamprou, Sigalis y Zissimopoulos [1] y Khuller, Purohit y Sarpatwar [2]. También aparece en la reciente encuesta de Narayanaswamy y Vijayaragunathan [3].