Conjunto dominante

En teoría de grafos , un conjunto dominante para un grafo $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 grafo $G$ dado y una entrada $K$ ; es un problema de decisión NP-completo clásico en la teoría de la complejidad computacional . ^[1] Por lo tanto, se cree que puede no haber un algoritmo eficiente que pueda calcular $γ($ $G$ $)$ para todos los grafos $G$ . Sin embargo, existen algoritmos de aproximación eficientes , así como algoritmos exactos eficientes para ciertas clases de grafos.

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

Definición formal

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

Todo grafo 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: . ${\estilo de visualización D=V=}$ $u\en V\setmenos 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 es conexo . Si S es un conjunto dominante conexo, se puede formar un árbol de expansión de G en el que S forma el conjunto de vértices no hoja del árbol; a la inversa, si T es cualquier árbol de expansión en un grafo con más de dos vértices, los vértices no hoja de T forman un conjunto dominante conexo. Por lo tanto, encontrar conjuntos dominantes conexos mínimos es equivalente a encontrar árboles de expansión con el máximo número posible de hojas.

Un conjunto dominante total (o conjunto fuertemente dominante ) es un conjunto de vértices tales que todos los vértices en el grafo, incluyendo los vértices en el conjunto dominante en sí, tienen un vecino en el conjunto dominante. ^[2] Es decir: para cada vértice , hay un vértice tal que . La figura (c) anterior muestra un conjunto dominante que es un conjunto dominante conexo y un conjunto dominante total; los ejemplos en las figuras (a) y (b) no son ninguno de los dos. A diferencia de un conjunto dominante simple, un conjunto dominante total puede no existir. Por ejemplo, un grafo 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 dominantes es un conjunto de aristas (pares de vértices) cuya unión es un conjunto dominante; dicho conjunto puede no existir (por ejemplo, un grafo 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 con aristas dominantes es un conjunto D de aristas, tal que cada arista que no está en D es adyacente a al menos una arista en D ; un conjunto de este tipo siempre existe (por ejemplo, el conjunto de todas las aristas es un conjunto con aristas dominantes).

Un conjunto k -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 k -tupla dominante es un conjunto de vértices tal que cada vértice en el grafo tiene al menos k vecinos en el conjunto (un conjunto dominante total es un conjunto dominante 1-tupla). Una aproximación $(1 + log n) de un conjunto$ k -tupla dominante mínimo se puede encontrar en tiempo polinomial. ^[3] Todo grafo admite un conjunto k -dominante (por ejemplo, el conjunto de todos los vértices); pero solo los grafos con grado mínimo $k - 1$ admiten un conjunto k -tupla dominante. Sin embargo, incluso si el grafo admite un conjunto k -tupla dominante, un conjunto k -tupla dominante mínimo puede ser casi k veces más grande que un conjunto k -dominante mínimo para el mismo grafo; ^[4] También se puede encontrar una aproximación $(1,7 + log Δ)$ de un conjunto k mínimo dominante en tiempo polinomial.

Un conjunto que domina a una estrella 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 ) interseca la estrella de algún vértice en D . Claramente, si G tiene vértices aislados entonces no tiene conjuntos que dominen a una estrella (ya que la estrella de vértices aislados está vacía). Si G no tiene vértices aislados, entonces cada conjunto dominante es un conjunto que domina a una estrella y viceversa. La distinción entre dominación a una estrella y dominación usual 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 ) tal 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 solo 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ónporconjuntos 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 grafo $G$ es el tamaño del conjunto dominante más pequeño que es un conjunto independiente. Equivalentemente, 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 grafos $G$ .

La desigualdad puede ser estricta - hay grafos $G$ para los cuales $γ (G) < i (G)$ . Por ejemplo, sea $G$ el grafo de estrella doble que consta de vértices ⁠ ⁠ $x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}$ , donde $p, q > 1$ . Las aristas 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 un conjunto dominante más pequeño. Si $p \leq q$ , entonces $i (G) = p + 1$ ya que ⁠ ⁠ $\{x_{1},\ldots ,x_{p},b\}$ es un conjunto dominante más pequeño que también es independiente (es un conjunto independiente maximal más pequeño).

Existen familias de grafos en las que $γ(G) = i (G)$ , es decir, todo conjunto independiente maximal mínimo es un conjunto dominante mínimo. Por ejemplo, $γ(G) = i (G)$ si $G$ es un grafo sin garras . ^[6]

Un grafo $G$ se denomina grafo de dominación perfecta si $γ (H) = i (H)$ en cada subgrafo inducido $H$ de $G$ . Dado que un subgrafo inducido de un grafo sin garras no tiene garras, se deduce que todo grafo sin garras también es de dominación perfecta. ^[7]

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

Dominacióndeconjuntos independientes

El número de dominación de independencia $iγ (G)$ de un grafo $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 grafos $G$ .

La desigualdad puede ser estricta - hay grafos $G$ para los cuales $iγ (G) < γ (G)$ . Por ejemplo, para algún entero $n$ , sea $G$ un grafo en el cual los vértices son las filas y columnas de un tablero $n$ -por- $n$ , y dos de tales vértices están conectados si y solo si se intersecan. Los únicos conjuntos independientes son conjuntos de solo filas o conjuntos de solo columnas, y cada uno de ellos puede estar dominado por un solo 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 grafo $G$ es el máximo, sobre todos los conjuntos independientes $A$ de $G$ , del conjunto independiente más pequeño que domina $a A$ . Las siguientes relaciones se cumplen para cualquier grafo $G$ : ${\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}$

Historia

El problema de dominación se estudió a partir de la década de 1950, pero la tasa de investigación sobre dominación aumentó significativamente a mediados de la década de 1970. En 1972, Richard Karp demostró que el problema de cobertura de conjuntos es NP-completo . Esto tuvo implicaciones inmediatas para el problema del conjunto dominante, ya que existen biyecciones directas de vértice a conjunto y de arista a intersección no disjunta entre los dos problemas. Esto demostró que el problema del conjunto dominante también es NP-completo . ^[9]

Algoritmos y complejidad computacional

El problema de cobertura de conjuntos es un problema NP-duro 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 mínimo dominante y el problema de cobertura de conjuntos . ^[10] Estas reducciones (ver más abajo) muestran que un algoritmo eficiente para el problema del conjunto mínimo dominante proporcionaría un algoritmo eficiente para el problema de cobertura de conjuntos, y viceversa. Además, las reducciones preservan la razón de aproximación : para cualquier α, un algoritmo de aproximación α en tiempo polinomial para conjuntos mínimos dominantes 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-completos . ^[11]

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

Reducciones en L

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

De dominar el set a cubrirlo

Dado un grafo $G = (V, E)$ con $V = {1, 2, ..., n},$ construya una instancia de cobertura de conjuntos $(U, S)$ como sigue: el universo $U$ es $V$ , y la familia de subconjuntos es $S = {S 1, S 2, ..., S n}$ tal que $S v$ consiste en el 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 una cobertura de conjunto 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 mínimos dominantes.

Por ejemplo, dado el grafo

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 de 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 cubrir el set a dominarlo

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};$ asumimos que $U$ y el conjunto índice $I$ son disjuntos. Construya un grafo $G = (V, E)$ como sigue: 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 grafo 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 lo tanto, $u$ está dominado por $i$ . Segundo, dado que $D$ debe ser no 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 reemplace 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 un conjunto cover; esto corresponde al conjunto dominante

D = {1, 4}.

D = {a, 3, 4}

es otro conjunto dominante para el grafo

G

. Dado

D

, podemos construir un conjunto dominante

X = { 1, 3, 4}

que no es mayor que

D

y que es un subconjunto de

I

. El conjunto dominante

X

corresponde a la cubierta de conjuntos

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

Casos especiales

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

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

Algoritmos exactos

Un conjunto mínimo dominante de un grafo $de n$ vértices se puede encontrar en tiempo $O (2 n n)$ inspeccionando todos los subconjuntos de vértices. Fomin, Grandoni y Kratsch (2009) muestran cómo encontrar un conjunto mínimo dominante en tiempo $O (1.5137 n)$ y espacio exponencial, y en tiempo $O (1.5264 n)$ y espacio polinomial. Un algoritmo más rápido, usando tiempo $O (1.5048 n)$ fue encontrado por van Rooij, Nederlof y van Dijk (2009), quienes también muestran que el número de conjuntos mínimos dominantes se puede calcular en este tiempo. El número de conjuntos mínimos dominantes es como máximo $1.7159 n$ y todos esos conjuntos se pueden enumerar en 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 más conocido y completo para la clase W[2] y se utiliza en muchas reducciones para demostrar la insolublebilidad de otros problemas. En particular, el problema no es solucionable 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 ninguna función $f$ a menos que la jerarquía W colapse a FPT=W[2].

Por otra parte, si el grafo de entrada es plano, el problema sigue siendo NP-duro, 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 los tiempos de ejecución que son 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 grafos libres de bicliques , una clase muy general de grafos dispersos que incluye los grafos 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]

Véase también

Conjetura de Vizing : relaciona el número de dominación de un producto cartesiano de grafos con el número de dominación de sus factores.
Problema con la cubierta del conjunto
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).
^ Förster (2013).
^ Meshulam, Roy (1 de mayo de 2003). "Números de dominación y homología". Journal of Combinatorial Theory, 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 grafos ponderados". Combinatorica . 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).
^ Parek (1991).
^ Papadimitriou y Yannakakis (1991).
^ Crescenzi y otros (2000).
^ Takamizawa, Nishizeki y Saito (1982).
^ Fomin y otros (2008).
^ Alber, becarios y Niedermeier (2004).
^ Fomin y Thilikos (2006).
^ Telle y Villanger (2012).
^ Dehne y otros (2006).

Referencias

Alber, Jochen; Fellows, 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 la dominación y los números de dominación independientes de un grafo", Discrete Mathematics , 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 NP.
Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena ; Rosamond, Frances (2006), "Nonblocker: Parameterized algorithmics for minimum dominating set" (PDF) , SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, República Checa, 21-27 de enero de 2006, Actas , Lecture Notes in Computer Science, vol. 3831, Springer, págs. 237–245, doi :10.1007/11611257_21, ISBN 978-3-540-31198-0.
Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Completitud en clases de aproximación más allá de APX" (PDF) , Theoretical Computer Science , 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: un estudio", Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR 1432221.
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "Un enfoque de medición y conquista 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, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Límites combinatorios mediante la medida y la conquista: delimitación de conjuntos dominantes mínimos y aplicaciones", 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 grafos planares: 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 de la dominación tolerante a fallas en grafos generales", Actas del décimo taller sobre 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 NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr. 0519066. OCLC 247570676., pág. 190, problema GT2.
Hedetniemi, ST; Laskar, RC (1990), "Bibliografía sobre dominación en grafos y algunas definiciones básicas de parámetros de dominación", Discrete Mathematics , 86 (1–3): 257–277, doi : 10.1016/0012-365X(90)90365-O.
Kann, Viggo (1992), Sobre la aproximabilidad de problemas de optimización NP-completos (PDF) . Tesis doctoral, Departamento de Análisis Numérico y Ciencias de la Computación, Instituto Real de Tecnología , Estocolmo.{{citation}}: Mantenimiento de CS1: postscript ( enlace ).
Klasing, Ralf; Laforest, Christian (2004), "Resultados de dureza y algoritmos de aproximación de dominancia de k-tuplas en grafos", Information Processing Letters , 89 (2): 75–83, doi :10.1016/j.ipl.2003.10.004.
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimización, aproximación y clases de 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 voraz para encontrar pequeños conjuntos dominantes en grafos", 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 caracterización PCP de probabilidad de error subconstante de NP", Proc. 29.° Simposio Anual de la ACM sobre Teoría de la Computación , ACM, págs. 475–484, doi :10.1145/258533.258641, ISBN 0-89791-888-6, Número de identificación del sujeto 15457604.
Takamizawa, K.; Nishizeki, T .; Saito, N. (1982), "Computabilidad en tiempo lineal de problemas combinatorios en grafos serie-paralelos", Journal of the ACM , 29 (3): 623–641, doi : 10.1145/322326.322328 , S2CID 16082154.
Telle, Jan Arne; Villanger, Yngve (2012), "Algoritmos FPT para dominación en grafos libres de biciclos", en Epstein, Leah; Ferragina, Paolo (eds.), Algoritmos – ESA 2012: 20.º Simposio Europeo Anual, Liubliana, Eslovenia, 10-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, ISBN 978-3-642-33089-6.
van Rooij, JMM; Nederlof, J.; van Dijk, TC (2009), "Inclusión/exclusión se encuentra con 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.

Lectura adicional

Grandoni, F. (2006), "Una nota sobre la complejidad del conjunto mínimo dominante", 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.