Conjunto dominante

En teoría de grafos , un conjunto dominante para un gráfico $G$ es un subconjunto $D$ de sus vértices, tal que cualquier vértice de $G$ está en $D$ o tiene un vecino en $D.$ El número de dominación $γ(G)$ es el número de vértices en un conjunto dominante más pequeño para $G$ .

El problema del conjunto dominante se refiere a probar si $γ(G) \leq K$ para un gráfico $G$ dado y una entrada $K$ ; Es un problema clásico de decisión NP-completa en la teoría de la complejidad computacional . ^[1] Por lo tanto , se cree que puede que no exista un algoritmo eficiente que pueda calcular $γ($ $G$ $)$ para todos los gráficos $G.$ Sin embargo, existen algoritmos de aproximación eficientes , así como algoritmos exactos eficientes para ciertas clases de gráficos.

Los conjuntos dominantes son de interés práctico en varias áreas. En las redes inalámbricas , los conjuntos dominantes se utilizan para encontrar rutas eficientes dentro de las redes móviles ad-hoc. También se han utilizado en el resumen de documentos y en el diseño de sistemas seguros para redes eléctricas .

Definicion formal

Dado un gráfico no dirigido $G = (V, E)$ , un subconjunto de vértices se llama conjunto dominante si para cada vértice hay un vértice tal que . $D\subseteq V$ $u\en V\setminus D$ $v\en D$ $(u,v)\en E$

Cada gráfico tiene al menos un conjunto dominante: si es el conjunto de todos los vértices, entonces, por definición, D es un conjunto dominante, ya que no hay ningún vértice . Un desafío más interesante es encontrar pequeños conjuntos dominantes. El número de dominación de $G$ se define como: . $D=V=$ $u\en V\setminus D$ $\gamma (G):=\min\{|D|:D{\text{ es un conjunto dominante de }}G\}$

Variantes

Un conjunto dominante conexo es un conjunto dominante que también está conexo . Si S es un conjunto dominante conexo, se puede formar un árbol generador de G en el que S forma el conjunto de vértices que no son hojas del árbol; por el contrario, si T es cualquier árbol generador en un gráfico con más de dos vértices, los vértices que no son hojas de T forman un conjunto dominante conectado. Por lo tanto, encontrar conjuntos dominantes mínimos conectados equivale a encontrar árboles expansivos con el máximo número posible de hojas.

Un conjunto dominante total (o conjunto fuertemente dominante ) es un conjunto de vértices tal que todos los vértices del gráfico, incluidos los vértices del conjunto dominante, tienen un vecino en el conjunto dominante. ^[2] Es decir: para cada vértice , existe un vértice tal que . La figura (c) anterior muestra un conjunto dominante que es un conjunto dominante conectado y un conjunto dominante total; los ejemplos de las figuras (a) y (b) no lo son. A diferencia de un conjunto dominante simple, es posible que no exista un conjunto dominante total. Por ejemplo, un gráfico con uno o más vértices y sin aristas no tiene un conjunto dominante total. El número de dominación fuerte de $G$ se define como: ; obviamente, . $u\en V$ $v\en D$ $(u,v)\en E$ $\gamma ^{strong}(G):=\min\{|D|:D{\text{ es un conjunto fuertemente dominante de }}G\}$ $\gamma ^{strong}(G)\geq \gamma (G)$

Un conjunto de aristas dominante es un conjunto de aristas (pares de vértices) cuya unión es un conjunto dominante; dicho conjunto puede no existir (por ejemplo, un gráfico con uno o más vértices y sin aristas no lo tiene). Si existe, entonces la unión de todas sus aristas es un conjunto fuertemente dominante. Por lo tanto, el tamaño más pequeño de un conjunto con aristas dominantes es al menos . $\gamma ^{fuerte}(G)/2$

Por el contrario, un conjunto de aristas dominantes es un conjunto D de aristas, de modo que cada arista que no está en D es adyacente a al menos una arista en D ; tal conjunto siempre existe (por ejemplo, el conjunto de todas las aristas es un conjunto que domina las aristas).

Un k -conjunto dominante es un conjunto de vértices tal que cada vértice que no está en el conjunto tiene al menos k vecinos en el conjunto (un conjunto dominante estándar es un conjunto 1-dominante). De manera similar, un conjunto dominante de k -tupla es un conjunto de vértices tal que cada vértice del gráfico tiene al menos k vecinos en el conjunto (un conjunto dominante total es un conjunto dominante de 1 tupla). Se puede encontrar una aproximación $(1 + log n) de un conjunto dominante de tupla$ k mínimo en tiempo polinomial. ^[3] Todo gráfico admite un k -conjunto dominante (por ejemplo, el conjunto de todos los vértices); pero sólo los gráficos con grado mínimo $k - 1$ admiten un conjunto dominante k -tupla. Sin embargo, incluso si el gráfico admite un conjunto dominante de k -tupla, un conjunto dominante mínimo de k -tupla puede ser casi k veces más grande que un conjunto mínimo k -dominante para el mismo gráfico; ^[4] También se puede encontrar una aproximación $(1,7 + log Δ)$ de un conjunto dominante k mínimo en tiempo polinomial.

Un conjunto dominante de estrellas es un subconjunto D de V tal que, para cada vértice v en V , la estrella de v (el conjunto de aristas adyacentes a v ) intersecta la estrella de algún vértice en D. Claramente, si G tiene vértices aislados , entonces no tiene conjuntos dominantes de estrellas (ya que la estrella de los vértices aislados está vacía). Si G no tiene vértices aislados, entonces todo conjunto dominante es un conjunto dominante en estrellas y viceversa. La distinción entre dominación estelar y dominación habitual es más sustancial cuando se consideran sus variantes fraccionarias. ^[5]

Una partición domática es una partición de los vértices en conjuntos dominantes disjuntos. El número domático es el tamaño máximo de una partición domática.

Un conjunto dominante eterno es una versión dinámica de dominación en la que se elige un vértice v en el conjunto dominante D y se reemplaza con un vecino u ( u no está en D ) de manera que el D modificado también es un conjunto dominante y este proceso puede repetirse. sobre cualquier secuencia infinita de elecciones de vértices v .

Conjuntos dominantes e independientes.

Los conjuntos dominantes están estrechamente relacionados con los conjuntos independientes : un conjunto independiente también es un conjunto dominante si y sólo si es un conjunto independiente máximo , por lo que cualquier conjunto independiente máximo en un gráfico es necesariamente también un conjunto dominante mínimo.

Dominación por conjuntos independientes

Un conjunto dominante puede ser o no un conjunto independiente. Por ejemplo, las figuras (a) y (b) anteriores muestran conjuntos dominantes independientes, mientras que la figura (c) ilustra un conjunto dominante que no es un conjunto independiente.

El número de dominación independiente $i (G)$ de un gráfico $G$ es el tamaño del conjunto dominante más pequeño que es un conjunto independiente. De manera equivalente, es el tamaño del conjunto independiente máximo más pequeño. El mínimo en $i (G)$ se toma sobre menos elementos (solo se consideran los conjuntos independientes), por lo que $γ (G) \leq i (G)$ para todos los gráficos $G.$

La desigualdad puede ser estricta: hay gráficos $G$ para los cuales $γ (G) < i (G)$ . Por ejemplo, sea $G$ el gráfico de estrella doble que consta de vértices , donde $p$ $,$ $q$ $> 1$ . Los bordes de $G$ se definen de la siguiente manera: cada $x$ $i$ es adyacente a $a$ , $a$ es adyacente a $b$ y $b$ es adyacente a cada $y$ $j$ . Entonces $γ($ $G$ $) = 2$ ya que ${$ $a$ $,$ $b$ $}$ es el conjunto dominante más pequeño. Si $p$ $\leq$ $q$ , entonces $i$ $($ $G$ $) =$ $p$ $+ 1$ ya que es un conjunto dominante más pequeño que también es independiente (es un conjunto independiente máximo más pequeño). $x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}$ $\{x_{1},\ldots,x_{p},b\}$

Hay familias de gráficos en las que $γ(G) = i (G)$ , es decir, todo conjunto mínimo máximo independiente es un conjunto mínimo dominante. Por ejemplo, $γ(G) = i (G)$ si $G$ es un gráfico sin garras . ^[6]

Un gráfico $G$ se llama gráfico de dominación perfecta si $γ (H$ ) $=$ $i$ $($ $H$ $)$ en cada subgrafo inducido $H$ de $G.$ Dado que un subgrafo inducido de un gráfico sin garras no tiene garras, se deduce que todos los gráficos sin garras también son de dominación perfecta. ^[7]

Para cualquier gráfico $G$ , su gráfico lineal $L (G)$ no tiene garras y, por lo tanto, un conjunto mínimo máximo independiente en $L (G)$ es también un conjunto mínimo dominante en $L (G)$ . Un conjunto independiente en $L (G)$ corresponde a un emparejamiento en $G$ , y un conjunto dominante en $L (G)$ corresponde a un conjunto dominante de borde en $G$ . Por lo tanto, una coincidencia mínima máxima tiene el mismo tamaño que un conjunto dominante de borde mínimo.

Dominación de conjuntos independientes.

El número de dominación de la independencia $iγ (G)$ de un gráfico $G$ es el máximo, sobre todos los conjuntos independientes $A$ de $G$ , del conjunto más pequeño que domina $A$ . ^[8] Dominar subconjuntos de vértices requiere potencialmente menos vértices que dominar todos los vértices, por lo que iγ $(G) \leq γ (G)$ para todos los gráficos $G.$

La desigualdad puede ser estricta: hay gráficos $G$ para los cuales $iγ (G) < γ (G)$ . Por ejemplo, para algún número entero $n$ , sea $G$ un gráfico en el que los vértices son las filas y columnas de un tablero de $n$ por $n$ , y dos de esos vértices están conectados si y sólo si se cruzan. Los únicos conjuntos independientes son conjuntos de sólo filas o conjuntos de sólo columnas, y cada uno de ellos puede estar dominado por un único vértice (una columna o una fila), por lo que $iγ (G) = 1$ . Sin embargo, para dominar todos los vértices necesitamos al menos una fila y una columna, por lo que $γ (G) = 2$ . Además, la relación entre $γ (G) / iγ (G)$ puede ser arbitrariamente grande. Por ejemplo, si los vértices de $G$ son todos los subconjuntos de cuadrados de un tablero de $n$ por $n , entonces todavía$ $iγ (G) = 1$ , pero $γ (G) = n$ . ^[8]

El número de dominación bi-independiente $iγi (G)$ de un gráfico $G$ es el máximo, sobre todos los conjuntos independientes $A$ de $G$ , del conjunto independiente más pequeño que domina $A$ . Las siguientes relaciones son válidas para cualquier gráfico $G$ :

{\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{alineado}}

Historia

El problema de la dominación se estudió a partir de la década de 1950, pero el ritmo de investigación sobre la dominación aumentó significativamente a mediados de la década de 1970. En 1972, Richard Karp demostró que el problema de la cobertura del conjunto era NP-completo . Esto tuvo implicaciones inmediatas para el problema del conjunto dominante, ya que hay vértices directos para establecer y bordes para biyecciones de intersección no disjuntas entre los dos problemas. Esto demostró que el problema del conjunto dominante también era NP-completo . ^[9]

Algoritmos y complejidad computacional.

El problema de cobertura de conjuntos es un problema NP-difícil bien conocido : la versión de decisión de la cobertura de conjuntos fue uno de los 21 problemas NP-completos de Karp . Existe un par de reducciones L en tiempo polinomial entre el problema del conjunto dominante mínimo y el problema de cobertura del conjunto . ^[10] Estas reducciones (ver más abajo) muestran que un algoritmo eficiente para el problema del conjunto dominante mínimo proporcionaría un algoritmo eficiente para el problema de cobertura del conjunto, y viceversa. Además, las reducciones preservan la relación de aproximación : para cualquier α, un algoritmo de aproximación α en tiempo polinomial para conjuntos dominantes mínimos proporcionaría un algoritmo de aproximación α en tiempo polinomial para el problema de cobertura de conjuntos y viceversa. De hecho, ambos problemas son Log-APX-complete . ^[11]

La aproximación de la cobertura de conjuntos también se comprende bien: se puede encontrar un factor de aproximación logarítmica utilizando un algoritmo codicioso simple , y encontrar un factor de aproximación sublogarítmico es NP-difícil. Más específicamente, el algoritmo codicioso proporciona un factor $1 + log| V |$ aproximación de un conjunto mínimo dominante, y ningún algoritmo de tiempo polinomial puede lograr un factor de aproximación mejor que $c log| V |$ para algunos $c > 0$ a menos que P = NP . ^[12]

reducciones L

Las dos reducciones siguientes muestran que el problema del conjunto mínimo dominante y el problema de cobertura del conjunto son equivalentes bajo reducciones L : dada una instancia de un problema, podemos construir una instancia equivalente del otro problema. ^[10]

De dominar el set a cubrir el set

Dado un gráfico $G = (V, E)$ con $V = {1, 2, ..., n},$ construya una instancia de cobertura de conjunto $(U, S)$ de la siguiente manera: el universo $U$ es $V$ y la familia de subconjuntos es $S = {S 1, S 2, ..., S n}$ tal que $S v$ consta del vértice $v$ y todos los vértices adyacentes a $v$ en $G$ .

Ahora bien, si $D$ es un conjunto dominante para $G$ , entonces $C = {S v : v \in D}$ es una solución factible del problema de cobertura de conjuntos, con $| C | = | D |$ . Por el contrario, si $C = {S v : v \in D}$ es una solución factible del problema de cobertura de conjuntos, entonces $D$ es un conjunto dominante para $G$ , con $| D | = | C |$ .

Por lo tanto, el tamaño de un conjunto mínimo dominante para $G$ es igual al tamaño de una cobertura de conjunto mínimo para $(U, S)$ . Además, existe un algoritmo simple que asigna un conjunto dominante a un conjunto de cobertura del mismo tamaño y viceversa. En particular, un algoritmo de aproximación α eficiente para la cobertura de conjuntos proporciona un algoritmo de aproximación α eficiente para conjuntos dominantes mínimos.

Por ejemplo, dado el gráfico

G

que se muestra a la derecha, construimos una instancia de cobertura de conjunto con el universo

U = {1, 2, ..., 6}

y los subconjuntos

S 1 = {1, 2, 5},

S 2 = {1, 2, 3, 5},

S 3 = {2, 3, 4, 6},

S 4 = {3, 4},

S 5 = {1, 2, 5, 6}

S 6 = {3, 5, 6}.

En este ejemplo,

D = {3, 5}

es un conjunto dominante para

G

; esto corresponde a la cobertura del conjunto

C = {S 3, S 5}.

Por ejemplo, el vértice

4 \in V

está dominado por el vértice

3 \in D

, y el elemento

4 \in U

está contenido en el conjunto

S 3 \in C.

De cobertura de set a set dominante

Sea $(S, U)$ una instancia del problema de cobertura de conjuntos con el universo $U$ y la familia de subconjuntos $S = {S i : i \in I};$ suponemos que $U$ y el conjunto de índices $I$ son disjuntos. Construya un gráfico $G = (V, E)$ de la siguiente manera: el conjunto de vértices es $V = I \cup U$ , hay una arista ${i, j} \in E$ entre cada par $i, j \in I$ , y también hay una arista ${i, u}$ para cada $i \in I$ y $u \in S i$ . Es decir, $G$ es un gráfico dividido : $I$ es una camarilla y $U$ es un conjunto independiente .

Ahora bien, si $C = {S i : i \in D}$ es una solución factible del problema de cobertura de conjuntos para algún subconjunto $D \subseteq I$ , entonces $D$ es un conjunto dominante para $G$ , con $| D | = | C |$ : Primero, para cada $u \in U$ hay un $i \in D$ tal que $u \in S i$ , y por construcción, $u$ e $i$ son adyacentes en $G$ ; por tanto $u$ está dominado por $i$ . En segundo lugar, dado que $D$ no debe estar vacío, cada $i \in I$ es adyacente a un vértice en $D.$

Por el contrario, sea $D$ un conjunto dominante para $G.$ Entonces es posible construir otro conjunto dominante $X$ tal que $| X | \leq | D |$ y $X \subseteq I$ : simplemente reemplaza cada $u \in D \cap U$ por un vecino $i \in I$ de $u$ . Entonces $C = {S i : i \in X}$ es una solución factible del problema de cobertura de conjuntos, con $| C | = | X | \leq | D |$ .

La ilustración de la derecha muestra la construcción para

U = {a, b, c, d, e}, I = {1, 2, 3, 4},

S 1 = {a, b, c},

S 2 = {a, b},

S 3 = {b, c, d}

S 4 = {c, d, e}.

En este ejemplo,

C = {S 1, S 4}

es una cobertura de conjunto; esto corresponde al conjunto dominante

D = {1, 4}.

D = {a, 3, 4}

es otro conjunto dominante para el gráfico

G

. Dado

D

,podemos construir un conjunto dominante

X = {1, 3, 4}

que no sea mayor que

D

y que sea un subconjunto de

I.

El conjunto dominante

X

corresponde al conjunto cobertura

C = {S 1, S 3, S 4}.

Casos especiales

Si el gráfico tiene un grado máximo Δ, entonces el algoritmo de aproximación codiciosa encuentra una aproximación $O (log Δ)$ de un conjunto dominante mínimo. Además, sea $d g$ la cardinalidad del conjunto dominante obtenido mediante una aproximación codiciosa y luego se cumple la siguiente relación, donde $N$ es el número de nodos y $M$ es el número de aristas en un gráfico no dirigido dado. ^[13] Para Δ fijo, esto califica como un conjunto dominante para la membresía de APX ; de hecho, es APX completo. ^[14] $d_{g}\leq N+1-{\sqrt {2M+1}}$

El problema admite un esquema de aproximación en tiempo polinomial (PTAS) para casos especiales como gráficos de discos unitarios y gráficos planos . ^[15] Se puede encontrar un conjunto mínimo dominante en tiempo lineal en gráficos en serie-paralelo . ^[dieciséis]

Algoritmos exactos

Se puede encontrar un conjunto dominante mínimo de un gráfico $de n -vértices en el tiempo$ $O (2 n n)$ inspeccionando todos los subconjuntos de vértices. Fomin, Grandoni y Kratsch (2009) muestran cómo encontrar un conjunto dominante mínimo en el tiempo $O (1,5137 n)$ y el espacio exponencial, y en el tiempo $O (1,5264 n)$ y el espacio polinomial. Van Rooij, Nederlof y van Dijk (2009) encontraron un algoritmo más rápido, que utiliza el tiempo $O (1,5048 n)$ , quienes también muestran que el número de conjuntos dominantes mínimos se puede calcular en este tiempo. El número de conjuntos dominantes mínimos es como máximo $1,7159 n$ y todos esos conjuntos se pueden enumerar en el tiempo $O (1,7159 n)$ . ^[17]

Complejidad parametrizada

Encontrar un conjunto dominante de tamaño $k$ juega un papel central en la teoría de la complejidad parametrizada. Es el problema completo más conocido para la clase W[2] y se utiliza en muchas reducciones para mostrar la intratabilidad de otros problemas. En particular, el problema no es manejable con parámetros fijos en el sentido de que no existe ningún algoritmo con tiempo de ejecución $f (k) n O(1)$ para cualquier función $f$ a menos que la jerarquía W colapse a FPT=W[2].

Por otro lado, si el gráfico de entrada es plano, el problema sigue siendo NP-difícil, pero se conoce un algoritmo de parámetros fijos. De hecho, el problema tiene un núcleo de tamaño lineal en $k$ , ^[18] y tiempos de ejecución exponenciales en √ k y cúbicos en $n$ se pueden obtener aplicando programación dinámica a una descomposición en ramas del núcleo. ^[19] De manera más general, el problema del conjunto dominante y muchas variantes del problema son manejables con parámetros fijos cuando se parametrizan tanto por el tamaño del conjunto dominante como por el tamaño del subgrafo bipartito completo prohibido más pequeño ; es decir, el problema es FPT en gráficos libres de bicliques , una clase muy general de gráficos dispersos que incluye los gráficos planos. ^[20]

El conjunto complementario de un conjunto dominante, un no bloqueador , se puede encontrar mediante un algoritmo de parámetros fijos en cualquier gráfico. ^[21]

Ver también

La conjetura de Vizing : relaciona el número de dominación de un producto cartesiano de gráficas con el número de dominación de sus factores.
Establecer problema de portada
número de esclavitud
No bloqueador : el complemento de un conjunto dominante.

Notas

^ Garey y Johnson (1979).
^ Oeste (2001), Sección 3.1.
^ Klasing y Laforest (2004).
^ Forster (2013).
^ Meshulam, Roy (1 de mayo de 2003). "Números de dominación y homología". Revista de teoría combinatoria, serie A. 102 (2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165.
^ Allan y Laskar (1978).
^ Faudree, Flandrin y Ryjáček (1997).
^ ab Aharoni, Ron; Berger, Eli; Ziv, Ran (1 de mayo de 2007). "Sistemas independientes de representantes en gráficos ponderados". Combinatoria . 27 (3): 253–267. doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
^ Hedetniemi y Laskar (1990).
^ ab Kann (1992), págs. 108-109.
^ Escoffier y Paschos (2006).
^ Raz y Safra (1997).
^ Parekh (1991).
^ Papadimitriou y Yannakakis (1991).
^ Crescenzi y col. (2000).
^ Takamizawa, Nishizeki y Saito (1982).
^ Fomín y col. (2008).
^ Alber, becarios y Niedermeier (2004).
^ Fomín y Thilikos (2006).
^ Telle y Villanger (2012).
^ Dehne y col. (2006).

Referencias

Alber, Jochen; Compañeros, Michael R ; Niedermeier, Rolf (2004), "Reducción de datos en tiempo polinomial para conjuntos dominantes", Journal of the ACM , 51 (3): 363–384, arXiv : cs/0207066 , doi :10.1145/990308.990309, S2CID 488501.
Allan, Robert B.; Laskar, Renu (1978), "Sobre los números de dominación y dominación independiente de un gráfico", Matemáticas discretas , 23 (2): 73–76, doi : 10.1016/0012-365X(78)90105-X.
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Conjunto dominante mínimo", Compendio de problemas de optimización de NP.
Dehne, Frank; Compañeros, Michael; Fernau, Henning; Prieto, Elena; Rosamond, Frances (2006), "Nonblocker: Algoritmia parametrizada para un conjunto dominante mínimo" (PDF) , SOFSEM 2006: 32ª Conferencia sobre tendencias actuales en teoría y práctica de la informática, Merin, República Checa, 21 al 27 de enero de 2006, Actas , Apuntes de conferencias sobre informática, vol. 3831, Springer, págs. 237–245, doi :10.1007/11611257_21.
Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Integridad en las clases de aproximación más allá de APX" (PDF) , Ciencias de la Computación Teórica , 359 (1–3): 369–377, doi : 10.1016/j.tcs.2006.05.023
Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Gráficos sin garras: una encuesta", Matemáticas discretas , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , SEÑOR 1432221.
Fomin, Fedor V.; Grandoni, Fabricio; Kratsch, Dieter (2009), "Un enfoque de medir y conquistar para el análisis de algoritmos exactos", Journal of the ACM , 56 (5): 25:1–32, doi :10.1145/1552285.1552286, S2CID 1186651.
Fomin, Fedor V.; Grandoni, Fabricio; Pyatkin, Artem; Stepanov, Alexey (2008), "Límites combinatorios mediante medir y conquistar: delimitar conjuntos y aplicaciones dominantes mínimos", ACM Transactions on Algorithms , 5 (1): 9:1–17, doi :10.1145/1435375.1435384, S2CID 2489447.
Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Conjuntos dominantes en gráficos planos: ancho de rama y aceleración exponencial", SIAM Journal on Computing , 36 (2): 281, doi :10.1137/S0097539702419649, S2CID 5232238.
Förster, Klaus-Tycho. (2013), "Aproximación a la dominación tolerante a fallos en gráficos generales", Proc. del Décimo Taller de Algorítmica Analítica y Combinatoria ANALCO , SIAM, págs. 25–32, doi :10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Serie de libros de ciencias matemáticas (1ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. SEÑOR 0519066. OCLC 247570676., pag. 190, problema GT2.
Hedetniemi, ST; Laskar, RC (1990), "Bibliografía sobre dominación en gráficos y algunas definiciones básicas de parámetros de dominación", Matemáticas discretas , 86 (1–3): 257–277, doi : 10.1016/0012-365X(90)90365-O.
Kann, Viggo (1992), Sobre la aproximabilidad de los problemas de optimización NP-completos (PDF) . Tesis doctoral, Departamento de Análisis Numérico y Ciencias de la Computación, Real Instituto de Tecnología , Estocolmo{{citation}}: Mantenimiento CS1: posdata ( enlace ).
Klasing, Ralf; Laforest, Christian (2004), "Resultados de dureza y algoritmos de aproximación de dominación de k-tuplas en gráficos", Information Processing Letters , 89 (2): 75–83, doi :10.1016/j.ipl.2003.10.004.
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Clases de optimización, aproximación y complejidad", Journal of Computer and System Sciences , 43 (3): 425–440, doi :10.1016/0022-0000(91)90023-X
Parekh, Abhay K. (1991), "Análisis de una heurística codiciosa para encontrar pequeños conjuntos dominantes en gráficos", Information Processing Letters , 39 (5): 237–240, doi :10.1016/0020-0190(91)90021-9 , hdl : 1721.1/1201
Raz, R .; Safra, S. (1997), "Una prueba de bajo grado de probabilidad de error subconstante y una caracterización de PCP de NP con probabilidad de error subconstante", Proc. 29º Simposio anual de ACM sobre teoría de la informática , ACM, págs. 475–484, doi :10.1145/258533.258641, ISBN 0-89791-888-6, S2CID 15457604.
Takamizawa, K.; Nishizeki, T .; Saito, N. (1982), "Computabilidad en tiempo lineal de problemas combinatorios en gráficos en series-paralelas", Journal of the ACM , 29 (3): 623–641, doi : 10.1145/322326.322328 , S2CID 16082154.
Telle, Jan Arne; Villanger, Yngve (2012), "Algoritmos FPT para la dominación en gráficos sin bicliques", en Epstein, Leah; Ferragina, Paolo (eds.), Algoritmos - ESA 2012: 20.º Simposio europeo anual, Liubliana, Eslovenia, 10 al 12 de septiembre de 2012, Actas , Lecture Notes in Computer Science , vol. 7501, Springer, págs. 802–812, doi :10.1007/978-3-642-33090-2_69.
van Rooij, JMM; Nederlof, J.; van Dijk, TC (2009), "La inclusión/exclusión se une a la medida y la conquista: algoritmos exactos para contar conjuntos dominantes", Proc. 17º Simposio Europeo Anual sobre Algoritmos, ESA 2009 , Lecture Notes in Computer Science, vol. 5757, Springer, págs. 554–565, doi :10.1007/978-3-642-04128-0_50, ISBN 978-3-642-04127-3.

Otras lecturas

Grandoni, F. (2006), "Una nota sobre la complejidad del conjunto dominante mínimo", Journal of Discrete Algorithms , 4 (2): 209–214, CiteSeerX 10.1.1.108.3223 , doi :10.1016/j.jda.2005.03 .002.
Guha, S.; Khuller, S. (1998), "Algoritmos de aproximación para conjuntos dominantes conectados" (PDF) , Algorithmica , 20 (4): 374–387, doi :10.1007/PL00009201, hdl : 1903/830 , S2CID 1249122.
Haynes, Teresa W .; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentos de dominación en gráficos , Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553.
Haynes, Teresa W .; Hedetniemi, Stephen; Slater, Peter (1998b), Dominación en gráficos: temas avanzados , Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061.
West, Douglas B. (2001), Introducción a la teoría de grafos (2 ed.), Pearson Education.