En la teoría de grafos , un conjunto dominante para un gráfico G = ( V , E ) es un subconjunto D de V de tal manera que cada vértice no en D es adyacente a al menos un miembro de D . El número 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 ) ≤ K para un gráfico G y una entrada K dados ; 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 no puede haber un algoritmo eficiente que encuentre un conjunto dominante más pequeño para todos los gráficos, aunque existen algoritmos de aproximación eficientes, así como algoritmos tanto eficientes como exactos para ciertas clases de gráficos.
Las figuras (a) - (c) de la derecha muestran tres ejemplos de conjuntos dominantes para una gráfica. En cada ejemplo, cada vértice blanco es adyacente a al menos un vértice rojo, y se dice que el vértice blanco está dominado por el vértice rojo. El número de dominación de este gráfico es 2: los ejemplos (b) y (c) muestran que hay un conjunto dominante con 2 vértices, y se puede comprobar que no hay un conjunto dominante con solo 1 vértice para este gráfico.
Historia
El problema de la dominación se estudió a partir de la década de 1950, pero la tasa 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 set era NP-completo . Esto tuvo implicaciones inmediatas para el problema del conjunto dominante, ya que existen biyecciones sencillas de vértice a conjunto y de borde a intersección no disjunta entre los dos problemas. Esto demostró que el problema de conjuntos dominante también era NP-completo . [2]
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.
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ó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 (sólo los conjuntos independientes se consideran), de modo γ ( G ) ≤ 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 x 1 , ..., x p , a , b , y 1 , ..., y q , donde p , q > 1. Las aristas de G están definidas de la siguiente manera: cada x i es adyacente a a , a es adyacente a b , y b es adyacente a cada b j . Entonces γ ( G ) = 2 ya que { a , b } es un conjunto dominante más pequeño. Si p ≤ q , entonces i ( G ) = p + 1 ya que { x 1 , ..., x p , b} es un conjunto dominante más pequeño que también es independiente (es un conjunto independiente máximo más pequeño).
Hay familias de gráficos en las que γ ( G ) = i ( G ), es decir, cada 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 . [3]
Un gráfico de G se denomina gráfico de dominación-perfecto si γ ( H ) = i ( H ) en cada inducida subgrafo 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 perfectos para la dominación. [4]
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 juego en G , y un conjunto dominante en L ( G corresponde) a un conjunto de aristas que domina en G . Por lo tanto, un emparejamiento máximo mínimo tiene el mismo tamaño que un conjunto dominante de borde mínimo.
Dominación de conjuntos independientes
El número dominación independencia iγ ( G ) de un grafo G es el máximo, sobre todo conjuntos independientes A de G , de los más pequeños conjunto dominante A . [5] subconjuntos dominantes de vértices requiere potencialmente menos vértices que domina todos los vértices, por lo iγ ( G ) ≤ gamma ( 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 entero n , deja que G sea un gráfico en el que los vértices son las filas y columnas de una n -by- n tabla, y dos de tales vértices si y sólo si están conectados de intersección. 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 los cuadrados de un n -by- n bordo, entonces todavía iγ ( G ) = 1, pero γ ( G ) = n . [5]
El número dominación bi-independiente iγi ( G ) de un grafo G es el máximo, sobre todo conjuntos independientes A de G , de los más pequeños conjunto dominante independiente A . Las siguientes relaciones son válidas para cualquier gráfico G :
Algoritmos y complejidad computacional
El problema de la cobertura del conjunto es un problema NP-duro bien conocido : la versión de decisión de la cobertura del conjunto fue uno de los 21 problemas NP-completos de Karp . Existe un par de reducciones L en tiempo polinómico entre el problema del conjunto dominante mínimo y el problema de la cobertura del conjunto . [6] 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 conservan la relación de aproximación : para cualquier α, un algoritmo de aproximación α de tiempo polinomial para conjuntos dominantes mínimos proporcionaría un algoritmo de aproximación α de tiempo polinómico para el problema de cobertura de conjuntos y viceversa. Ambos problemas son de hecho Log-APX-complete . [7]
La aproximabilidad de la cobertura de conjuntos también se comprende bien: se puede encontrar un factor de aproximación logarítmico mediante el uso de 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 dominante mínimo, 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 . [8]
L-reducciones
Las dos reducciones siguientes muestran que el problema del conjunto dominante mínimo y el problema de la cobertura del conjunto son equivalentes en las reducciones L : dada una instancia de un problema, podemos construir una instancia equivalente del otro problema. [6]
De conjunto dominante a cobertura de conjunto. 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 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 ∈ D } es una solución factible del problema de cobertura del conjunto, con | C | = | D |. Por el contrario, si C = { S v : v ∈ 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 dominante mínimo para G es igual al tamaño de la cobertura de un conjunto mínimo para ( U , S ). Además, existe un algoritmo simple que asigna un conjunto dominante a una cubierta de conjunto del mismo tamaño y viceversa. En particular, un algoritmo de aproximación α eficaz para la cobertura de conjuntos proporciona un algoritmo de aproximación α eficaz 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} y 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 ∈ V está dominado por el vértice 3 ∈ D , y el elemento 4 ∈ U está contenido en el conjunto S 3 ∈ C .
De la cobertura del set al 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 ∈ I }; asumimos que U y el conjunto de índices I son inconexos. Construya una gráfica G = ( V , E ) de la siguiente manera: el conjunto de vértices es V = I ∪ U , hay una arista { i , j } ∈ E entre cada par i , j ∈ I , y también hay una arista { i , u } para cada i ∈ I y u ∈ 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 ∈ D } es una solución factible del problema de cobertura de conjuntos para algún subconjunto D ⊆ I , entonces D es un conjunto dominante para G , con | D | = | C |: Primero, para cada u ∈ U hay un i ∈ D tal que u ∈ S i , y por construcción, u e i son adyacentes en G ; por tanto, u está dominado por i . En segundo lugar, puesto que D debe ser no vacío, cada i ∈ I es adyacente a un vértice en D .
Por el contrario, dejar que D sea un conjunto dominante de G . Entonces es posible construir otro conjunto X dominante tal que | X | ≤ | D | y X ⊆ I : simplemente reemplace cada u ∈ D ∩ U por un vecino i ∈ I de u . Entonces C = { S i : i ∈ X } es una solución factible del problema de cobertura del conjunto, con | C | = | X | ≤ | D |.
- La ilustración de la derecha muestra la construcción de 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 } y S 4 = { c , d , e }.
- En este ejemplo, C = { S 1 , S 4 } es una cubierta de conjunto; esto corresponde al conjunto dominante D = {1, 4}.
- D = { a , 3, 4} es otro conjunto dominante para el gráfico G . Dada 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 X dominante corresponde a la cobertura del conjunto C = { S 1 , S 3 , S 4 }.
Casos especiales
Si el gráfico tiene un grado máximo Δ, entonces el algoritmo de aproximación codicioso encuentra una aproximación O (log Δ) de un conjunto dominante mínimo. Además, sea d g la cardinalidad del conjunto dominante obtenido usando 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. [9] Para Δ fijo, esto califica como un conjunto dominante para la membresía APX ; de hecho, es APX-completo. [10]
El problema admite un esquema de aproximación de tiempo polinomial (PTAS) para casos especiales como gráficos de disco unitarios y gráficos planos . [11] Se puede encontrar un conjunto dominante mínimo en tiempo lineal en gráficos en serie-paralelos . [12]
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, usando O (1.5048 n ) tiempo , 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 ny todos estos conjuntos pueden enumerarse en el tiempo O (1,7159 n ). [13]
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 de la clase W [2] y se utiliza en muchas reducciones para mostrar la intratabilidad de otros problemas. En particular, el problema no es tratable 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 otro lado, si el gráfico de entrada es plano, el problema sigue siendo NP-hard, pero se conoce un algoritmo de parámetros fijos. De hecho, el problema tiene un núcleo de tamaño lineal en k , [14] y los tiempos de ejecución que son exponenciales en √ k y cúbicos en n pueden obtenerse aplicando programación dinámica a una descomposición de ramas del núcleo. [15] De manera más general, el problema del conjunto dominante y muchas variantes del problema son tratables 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áficas libres de biclices , una clase muy general de gráficas dispersas que incluye las gráficas planas. [dieciséis]
El conjunto complementario de un conjunto dominante, un no bloqueador , se puede encontrar mediante un algoritmo de parámetros fijos en cualquier gráfico. [17]
Variantes
Una subclase importante de los conjuntos dominantes es la clase de conjuntos dominantes conectados . Si S es un conjunto dominante conectado, se puede formar un árbol de expansión de G en el que S forma el conjunto de vértices no foliares del árbol; a la inversa, si T es cualquier árbol de expansión 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 conectados mínimos equivale a encontrar árboles en expansión con el máximo número posible de hojas.
Un conjunto dominante total es un conjunto de vértices de modo que todos los vértices del gráfico (incluidos los vértices del conjunto dominante) tienen un vecino en el conjunto dominante. 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 son ninguno.
Un conjunto dominante de k -tuplas es un conjunto de vértices tal que cada vértice del gráfico tiene al menos k vecinos en el conjunto. Se puede encontrar una aproximación (1 + log n) de un conjunto dominante mínimo de k tuplas en tiempo polinomial. [18] De manera similar, un conjunto que predomina en k es un conjunto de vértices de modo que cada vértice que no está en el conjunto tiene al menos k vecinos en el conjunto. Si bien cada gráfico admite un conjunto predominante de k , solo los gráficos con grado mínimo k - 1 admiten un conjunto dominante de k -tupla. Sin embargo, incluso si el gráfico admite k-tupla dominando conjunto, un mínimo k tupla dominando conjunto puede ser casi k veces tan grande como un mínimo k -dominating conjunto para el mismo gráfico; [19] Una aproximación (1.7 + log Δ) de un conjunto mínimo predominante de k también se puede encontrar en el tiempo polinomial.
Un conjunto de estrella que domina es un subconjunto D de V tal que, para cada vértice v en V , la estrella de v (el conjunto de los bordes adyacentes a v ) se cruza con la estrella de algunos vértice en D . Claramente, si G tiene vértices aislados, entonces no tiene conjuntos dominantes de estrellas (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 dominante de estrellas y viceversa. La distinción entre dominación de estrellas y dominación habitual es más sustancial cuando se consideran sus variantes fraccionarias. [20]
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 la 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 modo que el D modificado también es un conjunto dominante y este proceso puede repetirse. sobre cualquier secuencia infinita de opciones de vértices v .
Ver también
- Conjetura de Vizing : relaciona el número de dominación de un producto cartesiano de gráficos con el número de dominación de sus factores.
- Establecer problema de portada
- Número de esclavitud
Notas
- ^ Garey y Johnson (1979) .
- ^ Hedetniemi y Laskar (1990) .
- ^ Allan y Laskar (1978) .
- ^ Faudree, Flandrin y Ryjáček (1997) .
- ^ a b 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 .
- ↑ a b 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) .
- ^ Fomin y col. (2008) .
- ^ Alber, Fellows y Niedermeier (2004) .
- ^ Fomin y Thilikos (2006) .
- ^ Telle y Villanger (2012) .
- ^ Dehne y col. (2006) .
- ^ Klasing y Laforest (2004) .
- ^ Förster (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 .
Referencias
- Alber, Jochen; Becarios, Michael R ; Niedermeier, Rolf (2004), "Reducción de datos de tiempo polinomial para el conjunto dominante", 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 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: Algoritmos parametrizados 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 , Lecture Notes in Computer Science, 3831 , Springer, págs. 237–245, doi : 10.1007 / 11611257_21.
- Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Integridad en clases de aproximación más allá de APX", Informática teórica , 359 (1-3): 369-377, doi : 10.1016 / j.tcs.2006.05.023
- Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs - A survey", 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 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, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Límites combinatorios a través de medir y conquistar: límites de conjuntos y aplicaciones dominantes mínimos", Transacciones ACM sobre algoritmos , 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 del dominio tolerante a fallas en gráficos generales", Proc. del Décimo Taller de Algoritmia 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 NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5, 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 aproximación de problemas de optimización NP-completo (PDF) . Tesis de doctorado, Departamento de Análisis Numérico y Ciencias de la Computación, Real Instituto de Tecnología , EstocolmoCS1 maint: posdata ( enlace ).
- Klasing, Ralf; Laforest, Christian (2004), "Resultados de dureza y algoritmos de aproximación de la 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), "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 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
- Raz, R .; Safra, S. (1997), "Una prueba de bajo grado de probabilidad de error sub-constante y caracterización PCP de probabilidad de error sub-constante de NP", Proc. 29º Simposio Anual de ACM sobre Teoría de la Computación , 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 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 la dominación en gráficos libres de biclices", en Epstein, Leah; Ferragina, Paolo (eds.), Algorithms - ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, 10-12 de septiembre de 2012, Proceedings , Lecture Notes in Computer Science , 7501 , Springer, pp. 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 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, 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 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 la dominación en los 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.