Hispanopedia Wiki
Articulo de referencia

Conjunto independiente (teoría de grafos)

Los nueve vértices azules forman un conjunto independiente máximo para el grafo de Petersen generalizado GP(12,4). En teoría de grafos , un conjunto independiente , conjunto est...

Hispanopedia WikiContenido en espanolLectura gratuita
Los nueve vértices azules forman un conjunto independiente máximo para el grafo de Petersen generalizado GP(12,4).

En teoría de grafos , un conjunto independiente , conjunto estable , coclique o anticlique es un conjunto de vértices en un grafo , donde no hay dos adyacentes. Es decir, es un conjuntoS{\displaystyle S}de vértices tales que para cada dos vértices enS{\displaystyle S}, no hay ninguna arista que conecte los dos. De forma equivalente, cada arista en el grafo tiene como máximo un extremo enS{\displaystyle S}Un conjunto es independiente si y solo si es una camarilla en el complemento del grafo . El tamaño de un conjunto independiente es el número de vértices que contiene. Los conjuntos independientes también se han denominado "conjuntos internamente estables", de los cuales "conjunto estable" es una abreviatura. [ 1 ]

Un conjunto independiente maximal es un conjunto independiente que no es un subconjunto propio de ningún otro conjunto independiente.

Un conjunto independiente máximo es un conjunto independiente del mayor tamaño posible para un grafo dado.GRAMO{\displaystyle G}Este tamaño se denomina número de independencia deGRAMO{\displaystyle G}y se suele denotar porα(GRAMO){\displaystyle \alpha (G)}[ 2 ] El problema de optimización de encontrar dicho conjunto se denomina problema del conjunto independiente máximo. Es un problema fuertemente NP-difícil . [ 3 ] Por lo tanto, es improbable que exista un algoritmo eficiente para encontrar un conjunto independiente máximo de un grafo.

Todo conjunto independiente máximo es también máximo, pero la implicación inversa no tiene por qué ser cierta.

Propiedades

Relación con otros parámetros del gráfico

Un conjunto es independiente si y solo si es una camarilla en el complemento del grafo , por lo que ambos conceptos son complementarios. De hecho, los grafos suficientemente grandes sin camarillas grandes tienen conjuntos independientes grandes, un tema que se explora en la teoría de Ramsey .

Un conjunto es independiente si y solo si su complemento es una cubierta de vértices . [ 4 ] Por lo tanto, la suma del tamaño del conjunto independiente más grandeα(GRAMO){\displaystyle \alpha (G)}y el tamaño de una cobertura mínima de vérticesβ(GRAMO){\displaystyle \beta (G)}es igual al número de vértices del grafo.

Coloreado de vértices de un grafoGRAMO{\displaystyle G}corresponde a una partición de su conjunto de vértices en subconjuntos independientes. Por lo tanto, el número mínimo de colores necesarios en una coloración de vértices, el número cromáticoχ(GRAMO){\displaystyle \chi (G)}, es al menos el cociente del número de vértices enGRAMO{\displaystyle G}y el número independienteα(GRAMO){\displaystyle \alpha (G)}.

En un grafo bipartito sin vértices aislados, el número de vértices en un conjunto independiente máximo es igual al número de aristas en una cobertura de aristas mínima ; este es el teorema de Kőnig .

Conjunto independiente máximo

Un conjunto independiente que no es un subconjunto propio de otro conjunto independiente se llama maximal . Tales conjuntos son conjuntos dominantes . Cada grafo contiene como máximo 3 n /3 conjuntos independientes maximales, [ 5 ] pero muchos grafos tienen muchos menos. El número de conjuntos independientes maximales en grafos de ciclos de n vértices viene dado por los números de Perrin , y el número de conjuntos independientes maximales en grafos de caminos de n vértices viene dado por la secuencia de Padovan . [ 6 ] Por lo tanto, ambos números son proporcionales a potencias de 1,324718..., la razón plástica .

Encontrar conjuntos independientes

En informática , se han estudiado diversos problemas computacionales relacionados con conjuntos independientes.

  • En el problema del conjunto independiente máximo , la entrada es un grafo no dirigido y la salida es el conjunto independiente máximo en dicho grafo. Si existen varios conjuntos independientes máximos, solo es necesario obtener uno. Este problema a veces se denomina " empaquetamiento de vértices ".
  • En el problema del conjunto independiente de peso máximo , la entrada es un grafo no dirigido con pesos en sus vértices y la salida es un conjunto independiente con el peso total máximo. El problema del conjunto independiente máximo es el caso especial en el que todos los pesos son iguales a uno.
  • En el problema de la lista de conjuntos independientes máximos , la entrada es un grafo no dirigido y la salida es una lista de todos sus conjuntos independientes máximos. Este problema puede resolverse utilizando como subrutina un algoritmo para la lista de conjuntos independientes máximos, ya que el conjunto independiente máximo debe estar incluido entre todos los conjuntos independientes máximos.
  • En el problema de decisión de conjuntos independientes , la entrada es un grafo no dirigido y un número k , y la salida es un valor booleano : verdadero si el grafo contiene un conjunto independiente de tamaño k , y falso en caso contrario.

Los tres primeros problemas mencionados son importantes en las aplicaciones prácticas; el problema de decisión sobre conjuntos independientes no lo es, pero es necesario para aplicar la teoría de la NP-completitud a problemas relacionados con conjuntos independientes.

Conjuntos independientes máximos y camarillas máximas

El problema del conjunto independiente y el problema de la camarilla son complementarios: una camarilla en G es un conjunto independiente en el grafo complemento de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a ambos problemas. Por ejemplo, los resultados relacionados con el problema de la camarilla tienen los siguientes corolarios:

  • El problema de decisión de conjuntos independientes es NP-completo , por lo que no se cree que exista un algoritmo eficiente para resolverlo.
  • El problema del conjunto independiente máximo es NP-difícil y también es difícil de aproximar .

A pesar de la estrecha relación entre las camarillas máximas y los conjuntos independientes máximos en grafos arbitrarios, los problemas de conjuntos independientes y camarillas pueden ser muy diferentes cuando se restringen a clases especiales de grafos. Por ejemplo, para grafos dispersos (grafos en los que el número de aristas es como máximo una constante multiplicada por el número de vértices en cualquier subgrafo), la camarilla máxima tiene un tamaño acotado y puede encontrarse exactamente en tiempo lineal; [ 7 ] sin embargo, para las mismas clases de grafos, o incluso para la clase más restringida de grafos de grado acotado, encontrar el conjunto independiente máximo es MAXSNP-completo , lo que implica que, para alguna constante c (que depende del grado) es NP-difícil encontrar una solución aproximada que se encuentre dentro de un factor de c del óptimo. [ 8 ]

Algoritmos exactos

El problema del conjunto independiente máximo es NP-difícil. Sin embargo, se puede resolver de manera más eficiente que el tiempo O( n² ) que daría un algoritmo ingenuo de fuerza bruta que  examina cada subconjunto de vértices y comprueba si es un conjunto independiente.

A partir de 2017, se puede resolver en tiempo O(1,1996 n ) utilizando el espacio polinomial. [ 9 ] Cuando se restringe a grafos con grado máximo 3, se puede resolver en tiempo O(1,0836 n ). [ 10 ]

Para muchas clases de grafos, se puede encontrar un conjunto independiente de peso máximo en tiempo polinomial. Ejemplos famosos son los grafos libres de garras , [ 11 ] los grafos libres de P5 [ 12 ] y los grafos perfectos . [ 13 ] Para los grafos cordales , se puede encontrar un conjunto independiente de peso máximo en tiempo lineal. [ 14 ]

La descomposición modular es una buena herramienta para resolver el problema del conjunto independiente de peso máximo; el algoritmo de tiempo lineal en cografos es el ejemplo básico para ello. Otra herramienta importante son los separadores de cliques, como los descritos por Tarjan. [ 15 ]

El teorema de Kőnig implica que, en un grafo bipartito, el conjunto independiente máximo se puede encontrar en tiempo polinomial utilizando un algoritmo de emparejamiento bipartito.

Algoritmos de aproximación

En general, el problema del conjunto independiente máximo no puede aproximarse a un factor constante en tiempo polinomial (a menos que P = NP). De hecho, el problema del conjunto independiente máximo es, en general, poli-APX-completo , lo que significa que es tan difícil como cualquier problema que pueda aproximarse a un factor polinomial. [ 16 ] Sin embargo, existen algoritmos de aproximación eficientes para clases restringidas de grafos.

En grafos planares

En grafos planares , el conjunto independiente máximo puede aproximarse con cualquier razón de aproximación c  <  1 en tiempo polinomial; existen esquemas de aproximación similares en tiempo polinomial en cualquier familia de grafos cerrados bajo la toma de menores . [ 17 ]

En grafos de grado acotado

En grafos de grado acotado, se conocen algoritmos de aproximación efectivos con razones de aproximación que son constantes para un valor fijo del grado máximo; por ejemplo, un algoritmo voraz que forma un conjunto independiente maximal eligiendo, en cada paso, el vértice de grado mínimo en el grafo y eliminando sus vecinos, logra una razón de aproximación de (Δ+2)/3 en grafos con grado máximo  Δ. [ 18 ] Las cotas de dificultad de aproximación para tales instancias fueron demostradas en Berman y Karpinski (1999) . De hecho, incluso el conjunto independiente máximo en grafos 3-regulares 3-coloreables por aristas es APX-completo . [ 19 ]

En gráficos de intersección de intervalos

Un grafo de intervalos es un grafo cuyos nodos son intervalos unidimensionales (por ejemplo, intervalos de tiempo) y donde existe una arista entre dos intervalos si y solo si se intersecan. Un conjunto independiente en un grafo de intervalos es simplemente un conjunto de intervalos que no se superponen. El problema de encontrar el máximo de conjuntos independientes en grafos de intervalos se ha estudiado, por ejemplo, en el contexto de la planificación de tareas : dado un conjunto de tareas que deben ejecutarse en una computadora, encontrar el máximo conjunto de tareas que se pueden ejecutar sin interferir entre sí. Este problema se puede resolver exactamente en tiempo polinomial utilizando la planificación de plazo más temprano primero .

En gráficos de intersección geométrica

Un grafo de intersección geométrica es un grafo cuyos nodos son figuras geométricas y donde existe una arista entre dos figuras si y solo si se intersecan. Un conjunto independiente en un grafo de intersección geométrica es simplemente un conjunto de figuras disjuntas (que no se superponen). El problema de encontrar el máximo de conjuntos independientes en grafos de intersección geométrica se ha estudiado, por ejemplo, en el contexto de la colocación automática de etiquetas : dado un conjunto de ubicaciones en un mapa, encontrar el máximo de etiquetas rectangulares disjuntas cerca de dichas ubicaciones.

Encontrar un conjunto independiente máximo en grafos de intersección sigue siendo un problema NP-completo, pero es más fácil de aproximar que el problema general del conjunto independiente máximo. Una revisión reciente se puede encontrar en la introducción de Chan y Har-Peled (2012) .

En gráficos sin garra d

Un d-garra en un grafo es un conjunto de d + 1 vértices, uno de los cuales (el "centro") está conectado a los otros d vértices, pero los otros d vértices no están conectados entre sí. Un grafo libre de d - garras es un grafo que no tiene un subgrafo de d -garras. Consideremos el algoritmo que comienza con un conjunto vacío y agrega incrementalmente un vértice arbitrario siempre que no sea adyacente a ningún vértice existente. En los grafos libres de d- garras, cada vértice agregado invalida como máximo d − 1 vértices del conjunto independiente máximo; por lo tanto, este algoritmo trivial alcanza un algoritmo de aproximación ( d − 1) para el conjunto independiente máximo. De hecho, es posible obtener razones de aproximación mucho mejores:

  • Neuwohner [ 20 ] presentó un algoritmo de tiempo polinomial que, para cualquier constante ε>0, encuentra una aproximación ( d /2 − 1/63,700,992+ε) para el conjunto independiente de peso máximo en un grafo libre de d -garras.
  • Cygan [ 21 ] presentó un algoritmo de tiempo cuasi-polinomial que, para cualquier ε>0, alcanza una aproximación de (d+ε)/3.

Encontrar conjuntos independientes máximos

El problema de encontrar un conjunto independiente máximo se puede resolver en tiempo polinomial mediante un algoritmo voraz paralelo trivial . [ 22 ] Todos los conjuntos independientes máximos se pueden encontrar en tiempo O(3 n /3 ) = O(1,4423 n ).

Conteo de conjuntos independientes

Problema sin resolver en informática
¿Existe algún algoritmo de aproximación totalmente polinomial para el número de conjuntos independientes en grafos bipartitos?
Más problemas sin resolver en informática

El problema de conteo #IS pregunta, dado un grafo no dirigido, cuántos conjuntos independientes contiene. Este problema es intratable, es decir, es ♯P -completo, ya en grafos con grado máximo tres. [ 23 ] Se sabe además que, suponiendo que NP es diferente de RP , el problema no puede aproximarse de manera tratable en el sentido de que no tiene un esquema de aproximación totalmente polinomial con aleatorización (FPRAS), incluso en grafos con grado máximo seis; [ 24 ] sin embargo, sí tiene un esquema de aproximación totalmente polinomial (FPTAS) en el caso en que el grado máximo es cinco. [ 25 ] El problema #BIS, de contar conjuntos independientes en grafos bipartitos , también es ♯P -completo, ya en grafos con grado máximo tres. [ 26 ] No se sabe si #BIS admite un FPRAS. [ 27 ]

También se ha estudiado la cuestión del conteo de conjuntos independientes máximos .

Aplicaciones

El conjunto independiente máximo y su complemento, el problema de la cobertura mínima de vértices , están involucrados en la demostración de la complejidad computacional de muchos problemas teóricos. [ 28 ]

Véase también

  • Un conjunto independiente de aristas es un conjunto de aristas de las cuales no hay dos que tengan un vértice en común. Normalmente se le llama emparejamiento .
  • Una coloración de vértices es una partición del conjunto de vértices en conjuntos independientes.

Notas

  1. ↑ Korshunov (1974)
  2. ↑ Godsil y Royle (2001) , pág. 3.
  3. ^ Garey, señor; Johnson, DS (1 de julio de 1978). "Resultados de NP-completitud "fuertes": motivación, ejemplos e implicaciones" . Journal of the ACM . 25 (3): 499– 508. doi : 10.1145/322077.322090 . ISSN 0004-5411 . S2CID 18371269 .  
  4. ↑ Demostración: Un conjunto V de vértices es un conjunto independiente si y solo si cada arista del grafo es adyacente a como máximo un miembro de V, si y solo si cada arista del grafo es adyacente a al menos un miembro que no está en V, si y solo si el complemento de V es una cubierta de vértices.
  5. ↑ Moon y Moser (1965) .
  6. ↑ Füredi (1987) .
  7. ↑ Chiba y Nishizeki (1985) .
  8. ↑ Berman y Fujito (1995) .
  9. ↑ Xiao y Nagamochi (2017)
  10. ^ Xiao y Nagamochi (2013)
  11. ↑ Minty (1980) , Sbihi (1980) , Nakamura y Tamura (2001) , Faenza, Oriolo y Stauffer (2014) , Nobili y Sassano (2015)
  12. ^ Lokshtanov, Vatshelle y Villanger (2014)
  13. ^ Grötschel, Lovász & Schrijver (1993 , Capítulo 9: Conjuntos estables en gráficos)
  14. ↑ Frank (1976)
  15. ↑ Tarjan (1985)
  16. ↑ Bazgan, Cristina ; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completitud en clases de aproximación estándar y diferencial: Poly-(D)APX- y (D)PTAS-completitud" . Theoretical Computer Science . 339 ( 2–3 ): 272–292 . doi : 10.1016/j.tcs.2005.03.007 . S2CID 1418848 . 
  17. ^ Panadero (1994) ; Grohe (2003) .
  18. ↑ Halldórsson y Radhakrishnan (1997) .
  19. ↑ Chlebík, Miroslav; Chlebíková, Janka (2003). "Dificultad de aproximación para instancias de pequeña ocurrencia de problemas NP-difíciles" . Actas de la 5.ª Conferencia Internacional sobre Algoritmos y Complejidad . Lecture Notes in Computer Science. Vol. 2653. pp. 152–164 . doi : 10.1007/3-540-44849-7_21 . ISBN   978-3-540-40176-6.
  20. ↑ Neuwohner, Meike (2021-06-07), Un algoritmo de aproximación mejorado para el problema del conjunto independiente de peso máximo en grafos libres de d-garras , arXiv : 2106.03545
  21. ↑ Cygan, Marek (octubre de 2013). "Aproximación mejorada para la correspondencia tridimensional mediante búsqueda local de ancho de ruta limitado". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 509–518 . arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN  978-0-7695-5135-7. S2CID 14160646 . 
  22. ↑ Luby (1986) .
  23. ↑ Dyer, Martin; Greenhill, Catherine (1 de abril de 2000). "Sobre cadenas de Markov para conjuntos independientes" . Journal of Algorithms . 35 (1): 17– 49. doi : 10.1006/jagm.1999.1071 . ISSN 0196-6774 . 
  24. ↑ Sly, Allan (2010). "Transición computacional en el umbral de unicidad". 2010 IEEE 51.º Simposio Anual sobre Fundamentos de la Informática . págs. 287–296 . arXiv : 1005.5584 . doi : 10.1109/FOCS.2010.34 . ISBN  978-1-4244-8525-3. S2CID 901126 . 
  25. ↑ Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Aproximación mediante decaimiento de correlación cuando falla la mezcla espacial fuerte" . SIAM Journal on Computing . 48 (2): 279–349 . arXiv : 1510.09193 . doi : 10.1137/16M1083906 . ISSN 0097-5397 . S2CID 131975798 .  
  26. ↑ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (24 de septiembre de 2007). "Complejidad computacional de problemas de conteo en grafos planares 3-regulares" . Theoretical Computer Science . Theory and Applications of Models of Computation. 384 (1): 111– 125. doi : 10.1016/j.tcs.2007.05.023 . ISSN 0304-3975 . , citado en Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01). "Una perspectiva de parámetros fijos sobre #BIS" . Algorithmica . 81 (10): 3844– 3864. arXiv : 1702.05543 . doi : 10.1007/s00453-019-00606-4 . hdl : 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541 . S2CID 3626662 .  
  27. ↑ Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi (ed.). Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Society for Industrial and Applied Mathematics. arXiv : 1906.01666 . doi : 10.1137/1.9781611975994.88 . ISBN 978-1-61197-599-4. S2CID 174799567 . 
  28. ↑ Skiena, Steven S. (2012). Manual de diseño de algoritmos . Springer. ISBN 978-1-84800-069-8OCLC 820425142​​ 

Referencias

  • Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en grafos planares", Journal of the ACM , 41 (1): 153–180 , doi : 10.1145/174644.174650 , S2CID 9706753 .
  • Berman, Piotr; Fujito, Toshihiro (1995), "Sobre las propiedades de aproximación del problema del conjunto independiente para grafos de grado 3", Algorithms and Data Structures , Lecture Notes in Computer Science, vol.  955, Springer-Verlag , pp. 449–460 , doi : 10.1007/3-540-60220-8_84 , ISBN  978-3-540-60220-0.
  • Berman, Piotr; Karpinski, Marek (1999), "Sobre algunos resultados de inaproximabilidad más estrictos", Autómatas, lenguajes y programación, 26.º Coloquio Internacional, ICALP'99 Praga , Lecture Notes in Computer Science , vol.  1644, Praga: Springer-Verlag , pp. 200–209 , doi : 10.1007/3-540-48523-6 , ISBN  978-3-540-66224-2, S2CID 23288736 
  • Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan MM (2010), "Un método ascendente y algoritmos rápidos para MAX INDEPENDENT SET", Algorithm Theory - SWAT 2010 , Lecture Notes in Computer Science, vol.  6139, Berlín: Springer, pp. 62–73 , Bibcode : 2010LNCS.6139...62B , doi : 10.1007/978-3-642-13731-0_7 , ISBN  978-3-642-13730-3, MR 2678485 .
  • Chan, TM (2003), "Esquemas de aproximación en tiempo polinomial para el empaquetado y perforación de objetos gruesos", Journal of Algorithms , 46 (2): 178– 189, CiteSeerX 10.1.1.21.5344 , doi : 10.1016/s0196-6774(02)00294-8 .
  • Chan, TM ; Har-Peled, S. (2012), "Algoritmos de aproximación para el conjunto independiente máximo de pseudodiscos", Discrete & Computational Geometry , 48 (2): 373, arXiv : 1103.1431 , CiteSeerX 10.1.1.219.2131 , doi : 10.1007/s00454-012-9417-5 , S2CID 38183751  .
  • Chiba, N.; Nishizeki, T. (1985), "Arboricidad y algoritmos de listado de subgrafos", SIAM Journal on Computing , 14 (1): 210– 223, doi : 10.1137/0214017 , S2CID 207051803 .
  • Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Esquemas de aproximación en tiempo polinomial para grafos de intersección geométrica", SIAM Journal on Computing , 34 (6): 1302, doi : 10.1137/s0097539702402676.
  • Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Resolución del problema del conjunto estable ponderado en grafos sin garras" , Journal of the ACM , 61 (4): 1– 41, doi : 10.1145/2629600 , S2CID 1995056 .
  • 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): 1– 32, doi : 10.1145/1552285.1552286 , S2CID 1186651 , artículo n.º 25,   .
  • Frank, András ( 1976), "Algunos algoritmos polinomiales para ciertos grafos e hipergrafos", Congressus Numerantium , XV : 211–226.
  • Füredi, Zoltán (1987), "El número de conjuntos independientes máximos en grafos conectados", Journal of Graph Theory , 11 (4): 463–470 , doi : 10.1002/jgt.3190110403.
  • Godsil, Chris ; Royle, Gordon (2001), Teoría algebraica de grafos , Nueva York: Springer , ISBN 978-0-387-95220-8.
  • Grohe, Martin (2003), "Algoritmos locales de ancho de árbol, menores excluidos y aproximación", Combinatorica , 23 (4): 613–632 , arXiv : math/0001128 , doi : 10.1007/s00493-003-0037-9 , S2CID 11751235 .
  • Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol.  2 (2ª  ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419 .
  • Halldórsson, MM; Radhakrishnan, J. (1997), "La codicia es buena: Aproximación de conjuntos independientes en grafos dispersos y de grado limitado", Algorithmica , 18 (1): 145– 163, CiteSeerX 10.1.1.145.4523 , doi : 10.1007/BF02523693 , S2CID 4661668  .
  • Korshunov, AD (1974), "Coeficiente de estabilidad interna", Kibernetika (en ucraniano), 10 (1): 17– 28, doi : 10.1007/BF01069014 , S2CID 120343511 .
  • Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Conjuntos independientes en grafos libres de P 5 en tiempo polinomial", SODA (Simposio sobre algoritmos discretos) : 570–581.
  • Luby, Michael (1986), "Un algoritmo paralelo simple para el problema del conjunto independiente máximo", SIAM Journal on Computing , 15 (4): 1036–1053 , CiteSeerX 10.1.1.225.5475 , doi : 10.1137/0215074 , MR 0861369  .
  • Minty, GJ (1980), "Sobre conjuntos independientes máximos de vértices en grafos sin garras", Journal of Combinatorial Theory, Serie B , 28 (3): 284–304 , doi : 10.1016/0095-8956(80)90074-x.
  • Moon, JW; Moser, Leo (1965), "Sobre las camarillas en grafos", Israel Journal of Mathematics , 3 (1): 23– 28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414  .
  • Nakamura, D.; Tamura, A. (2001), "Una revisión del algoritmo de Minty para encontrar un conjunto estable de peso máximo en un grafo libre de garras", Journal of Operations Research Society Japan , 44 (2): 194– 204, doi : 10.15807/jorsj.44.194.
  • Nobili, P.; Sassano, A. (2015), Un algoritmo O(n^2 log n) para el problema del conjunto estable ponderado en grafos sin garras , arXiv : 1501.05775 , Bibcode : 2015arXiv150105775N
  • Robson, JM (1986), "Algoritmos para conjuntos independientes máximos", Journal of Algorithms , 7 (3): 425– 440, doi : 10.1016/0196-6774(86)90032-5.
  • Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité Maximum dans un graphe sans étoile", Matemáticas discretas (en francés), 29 (1): 53– 76, doi : 10.1016/0012-365X(90)90287-R , SEÑOR 0553650 .
  • Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Algoritmos exactos para el conjunto independiente máximo", Information and Computation , 255 : 126–146 , arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001 , S2CID 1714739 .
  • Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confinando conjuntos y evitando casos de cuello de botella: Un algoritmo simple de conjunto independiente máximo en grafos de grado 3", Theoretical Computer Science , 469 : 92–104 , doi : 10.1016/j.tcs.2012.09.022.
  • Tarjan, RE (1985), "Descomposición por separadores de cliques", Matemáticas Discretas , 55 (2): 221– 232, doi : 10.1016/0012-365x(85)90051-2.
  • Weisstein, Eric W. "Conjunto máximo de vértices independientes" . MathWorld .
  • Puntos de referencia desafiantes para el máximo número de camarillas, el máximo conjunto independiente, la mínima cobertura de vértices y la coloración de vértices. Archivado el 29/05/2013 en la Wayback Machine.
  • Conjunto independiente y portada de Vertex , Hanan Ayad.
Lecturas relacionadas
6 articulos
Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Glosario de teoría de grafosEste es un glosario de teoría de grafos . La teoría de grafos es el estudio de los grafos , sistemas de nodos o vértices conectados en pares por lí...Clique (teoría de grafos)Clique (teoría de grafos)En el área matemática de la teoría de grafos , una camarilla (/ˈk l iː k/ o /ˈk l ɪ k/ ) es un subconjunto de vértices de un grafo no dirigido tal ...Complement graphComplement graphIn the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices...