Conjunto independiente (teoría de grafos)
Vértices no relacionados en gráficos
Los nueve vértices azules forman un conjunto máximo independiente para el gráfico 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 , de los cuales ninguno es adyacente. Es decir, es un conjunto de vértices tal que por cada dos vértices en , no hay ninguna arista que conecte los dos. Equivalentemente, cada arista en el grafo tiene como máximo un punto final en . Un conjunto es independiente si y solo si es una clique 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 llamado "conjuntos internamente estables", de los cuales "conjunto estable" es una abreviatura. [1] S {\estilo de visualización S} S {\estilo de visualización S} S {\estilo de visualización S}

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 gráfico dado . Este tamaño se denomina número de independencia de y generalmente se denota por . [2] El problema de optimización para encontrar dicho conjunto se denomina problema del conjunto independiente máximo. Es un problema fuertemente NP-hard . [3] Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto independiente máximo de un gráfico. GRAMO {\estilo de visualización G} GRAMO {\estilo de visualización G} alfa ( GRAMO ) {\displaystyle \alpha (G)}

Todo conjunto independiente máximo también es máximo, pero la implicación inversa no se cumple necesariamente.

Propiedades

Pares con problemas de cobertura/embalaje
Problemas de cobertura Problemas de embalaje
Cobertura mínima del conjunto Embalaje máximo del conjunto
Cobertura mínima del borde Coincidencia máxima
Cobertura mínima de vérticesConjunto independiente máximo
Cobertura de contenedores Embalaje de contenedores
Cobertura poligonal Embalaje rectangular

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

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

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

La coloración de los vértices de un grafo 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 , es al menos el cociente del número de vértices en y el número independiente . GRAMO {\estilo de visualización G} χ ( GRAMO ) {\displaystyle \chi (G)} GRAMO {\estilo de visualización G} alfa ( GRAMO ) {\displaystyle \alpha (G)}

En un gráfico 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 un recubrimiento de aristas mínimo ; este es el teorema de König .

Conjunto independiente maximo

Un conjunto independiente que no es un subconjunto propio de otro conjunto independiente se denomina 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 ciclo de n -vértices está dado por los números de Perrin , y el número de conjuntos independientes maximales en grafos de camino de n -vértices está 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 varios problemas computacionales relacionados con conjuntos independientes.

  • En el problema del conjunto máximo independiente , la entrada es un grafo no dirigido y la salida es un conjunto máximo independiente en el grafo. Si hay varios conjuntos máximos independientes, solo es necesario que uno sea la salida. Este problema a veces se denomina " empaquetamiento de vértices ".
  • En el problema de conjuntos independientes 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 máximo peso total. El problema de conjuntos independientes de peso máximo es el caso especial en el que todos los pesos son uno.
  • En el problema de listado 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. El problema de conjuntos independientes máximos se puede resolver utilizando como subrutina un algoritmo para el problema de listado de conjuntos independientes máximos, porque el conjunto independiente máximo debe estar incluido entre todos los conjuntos independientes máximos.
  • En el problema de decisión de conjunto independiente , la entrada es un gráfico no dirigido y un número k , y la salida es un valor booleano : verdadero si el gráfico contiene un conjunto independiente de tamaño k , y falso en caso contrario.

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

Máximo de conjuntos independientes y máximo de camarillas

El problema de los conjuntos independientes y el problema de la camarilla son complementarios: una camarilla en G es un conjunto independiente en el grafo complementario de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los dos 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 y, por lo tanto, no se cree que exista un algoritmo eficiente para resolverlo.
  • El problema del conjunto máximo independiente es NP-difícil y también es difícil de aproximar .

A pesar de la estrecha relación entre los grupos máximos y los conjuntos independientes máximos en grafos arbitrarios, los problemas de grupos independientes y grupos pueden ser muy diferentes cuando se limitan 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), el grupo máximo tiene un tamaño acotado y se puede encontrar 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 (dependiendo 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-hard. Sin embargo, se puede resolver de manera más eficiente que el tiempo O( n 2  2 n ) que se obtendría con un algoritmo de fuerza bruta ingenuo que examina cada subconjunto de vértices y verifica 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 gráficos 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 del peso máximo en tiempo polinomial. Ejemplos famosos son los grafos sin garras , [11] los grafos sin P 5 [12] y los grafos perfectos . [13] Para los grafos cordales , se puede encontrar un conjunto independiente del peso máximo en tiempo lineal. [14]

La descomposición modular es una buena herramienta para resolver el problema de los conjuntos independientes de peso máximo; el algoritmo de tiempo lineal en cografos es el ejemplo básico de ello. Otra herramienta importante son los separadores de camarillas, como los describe 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 correspondencia bipartita.

Algoritmos de aproximación

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

En grafos planares

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

En gráficos de grado acotado

En los grafos de grado acotado, se conocen algoritmos de aproximación eficaces 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 máximo 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] Los límites de dureza de aproximación para tales casos fueron probados en Berman & Karpinski (1999). De hecho, incluso el conjunto independiente máximo en grafos 3-regulares de 3 aristas coloreables es APX-completo . [19]

En gráficos de intersección de intervalos

Un gráfico de intervalos es un gráfico en el que los nodos son intervalos unidimensionales (por ejemplo, intervalos de tiempo) y hay una arista entre dos intervalos si y solo si se intersecan. Un conjunto independiente en un gráfico de intervalos es simplemente un conjunto de intervalos que no se superponen. El problema de encontrar conjuntos independientes máximos en gráficos de intervalos se ha estudiado, por ejemplo, en el contexto de la programación de trabajos : dado un conjunto de trabajos que se deben ejecutar en una computadora, encuentre un conjunto máximo de trabajos que se puedan ejecutar sin interferir entre sí. Este problema se puede resolver exactamente en tiempo polinomial utilizando la programación de fecha límite más temprana .

En gráficos de intersección geométrica

Un gráfico de intersección geométrica es un gráfico en el que los nodos son formas geométricas y hay una arista entre dos formas si y solo si se intersecan. Un conjunto independiente en un gráfico de intersección geométrica es simplemente un conjunto de formas disjuntas (no superpuestas). El problema de encontrar el máximo de conjuntos independientes en gráficos 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, encuentre un conjunto máximo de etiquetas rectangulares disjuntas cerca de estas 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. Se puede encontrar un estudio reciente en la introducción de Chan y Har-Peled (2012).

En gráficos sin garra D

Una 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 sin d-garra es un grafo que no tiene un subgrafo con d -garra. Considere el algoritmo que comienza con un conjunto vacío y le agrega de manera incremental un vértice arbitrario siempre que no sea adyacente a ningún vértice existente. En los grafos sin d -garra, cada vértice agregado invalida como máximo d -1 vértices del conjunto independiente máximo; por lo tanto, este algoritmo trivial obtiene un algoritmo de aproximación ( d -1) para el conjunto independiente máximo. De hecho, es posible obtener proporciones 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 del peso máximo en un gráfico libre de d -claw.
  • Cygan [21] presentó un algoritmo de tiempo cuasi-polinomial que, para cualquier ε>0, alcanza una aproximación (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 trivial paralelo voraz . [22] Todos los conjuntos independientes máximos se pueden encontrar en el tiempo O(3 n /3 ) = O(1.4423 n ).

Contando conjuntos independientes

Problema sin resolver en informática :
¿Existe un algoritmo de aproximación en tiempo completamente polinomial para el número de conjuntos independientes en gráficos 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 se puede aproximar de manera tratable en el sentido de que no tiene un esquema de aproximación de tiempo polinomial completo con aleatorización (FPRAS), incluso en grafos con grado máximo seis; [24] sin embargo, tiene un esquema de aproximación de tiempo polinomial completo (FPTAS) en el caso en que el grado máximo sea 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 recuento de conjuntos independientes máximos .

Aplicaciones

El conjunto independiente máximo y su complemento, el problema de cobertura mínima de vértices , intervienen en la demostración de la complejidad computacional de muchos problemas teóricos. [28] También sirven como modelos útiles para problemas de optimización del mundo real, por ejemplo, el conjunto independiente máximo es un modelo útil para descubrir componentes genéticos estables para diseñar sistemas genéticos diseñados . [29]

Véase también

  • Un conjunto de aristas independientes es un conjunto de aristas en el que no hay dos que tengan un vértice en común. Se suele llamar conjunto coincidente .
  • 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, MR; Johnson, DS (1 de julio de 1978). "Resultados de NP-Completitud "fuertes": motivación, ejemplos e implicaciones". Revista de la 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. ^ Luna 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. ^ Franco (1976)
  15. ^ Tarjan (1985)
  16. ^ Bazgan, Cristina ; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completitud en clases de aproximación estándar y diferencial: Completitud poli-(D)APX- y (D)PTAS". Ciencias Informáticas Teóricas . 339 (2–3): 272–292. doi : 10.1016/j.tcs.2005.03.007 . S2CID  1418848.
  17. ^ Banco de Inglaterra (1994);
  18. ^ Halldórsson y Radhakrishnan (1997).
  19. ^ Chlebík, Miroslav; Chlebíková, Janka (2003). "Dureza de aproximación para instancias de ocurrencia pequeña de problemas NP-difíciles". Actas de la 5.ª Conferencia internacional sobre algoritmos y complejidad . Apuntes de clase en informática. Vol. 2653. págs. 152–164. doi :10.1007/3-540-44849-7_21. ISBN 978-3-540-40176-6.
  20. ^ Neuwohner, Meike (7 de junio de 2021), Un algoritmo de aproximación mejorado para el problema de conjunto independiente de peso máximo en gráficos libres d-Claw , 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 . págs. 509–518. arXiv : 1304.1424 . doi :10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7.S2CID14160646  .​
  22. ^ Luby (1986).
  23. ^ Dyer, Martin; Greenhill, Catherine (1 de abril de 2000). "Sobre cadenas de Markov para conjuntos independientes". Revista de algoritmos . 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 51st Annual Symposium on Foundations of Computer Science . págs. 287–296. 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 a través de la desintegración de la correlación cuando falla la mezcla espacial fuerte". Revista SIAM de Computación . 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 planos 3-regulares". Ciencias de la Computación Teórica . Teoría y Aplicaciones de Modelos de Computación. 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 (1 de octubre de 2019). "Una perspectiva de parámetros fijos sobre #BIS". Algorithmica . 81 (10): 3844–3864. 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: Sociedad de Matemáticas Industriales y Aplicadas. arXiv : 1906.01666 . doi :10.1137/1.9781611975994.88. ISBN . 978-1-61197-599-4.S2CID174799567  .​
  28. ^ Skiena, Steven S. (2012). Manual de diseño de algoritmos . Springer. ISBN 978-1-84800-069-8.OCLC 820425142  .
  29. ^ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (13 de julio de 2020). "Diseño automatizado de miles de partes no repetitivas para la ingeniería de sistemas genéticos estables". Nature Biotechnology . 38 (12): 1466–1475. doi :10.1038/s41587-020-0584-2. ISSN  1546-1696. PMID  32661437. S2CID  220506228.

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 de conjuntos independientes para grafos de grado 3", Algorithms and Data Structures , Lecture Notes in Computer Science, vol. 955, Springer-Verlag , págs. 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", Automata, Languages ​​and Programming, 26.° Coloquio Internacional, ICALP'99 Praga , Lecture Notes in Computer Science , vol. 1644, Praga: Springer-Verlag , págs. 200–209, doi :10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, Número de identificación del sujeto  23288736
  • Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan MM (2010), "Un método de abajo hacia arriba y algoritmos rápidos para MAX INDEPENDENT SET", Algorithm Theory - SWAT 2010 , Lecture Notes in Computer Science, vol. 6139, Berlín: Springer, págs. 62–73, Bibcode :2010LNCS.6139...62B, doi :10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, Sr.  2678485.
  • Chan, TM (2003), "Esquemas de aproximación en tiempo polinomial para empaquetar y perforar objetos gordos", 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 máximo independiente de pseudodiscos", Geometría discreta y computacional , 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), "Algoritmos de arboricidad y 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 gráficos 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 medida y conquista 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 conexos", Journal of Graph Theory , 11 (4): 463–470, doi :10.1002/jgt.3190110403.
  • Godsil, Chris ; Royle, Gordon (2001), Teoría de grafos algebraicos , Nueva York: Springer , ISBN 978-0-387-95220-8.
  • Grohe, Martin (2003), "Ancho de árbol local, menores excluidos y algoritmos de 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, Sr.  1261419.
  • Halldórsson, MM; Radhakrishnan, J. (1997), "La codicia es buena: aproximación de conjuntos independientes en grafos dispersos y de grado acotado", 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 de vértices independientes máximos 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 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 gráfico sin 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 de 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 máximo independiente", Información y computación , 255 : 126–146, arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001, S2CID  1714739.
  • Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confinar conjuntos y evitar 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 camarillas", Discrete Mathematics , 55 (2): 221–232, doi : 10.1016/0012-365x(85)90051-2.
  • Weisstein, Eric W. "Conjunto de vértices independientes máximos". MathWorld .
  • Puntos de referencia desafiantes para camarilla máxima, conjunto independiente máximo, cobertura mínima de vértices y coloración de vértices Archivado el 29 de mayo de 2013 en Wayback Machine
  • Conjunto independiente y portada de Vertex, Hanan Ayad.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Conjunto_independiente_(teoría_de_grafos)&oldid=1251591436"