En teoría de grafos , un conjunto máximo independiente (MIS) o conjunto estable máximo es un conjunto independiente que no es un subconjunto de ningún otro conjunto independiente. En otras palabras, no hay vértice fuera del conjunto independiente que pueda unirlo porque es máximo con respecto a la propiedad del conjunto independiente.
Por ejemplo, en el gráfico , un camino con tres vértices , , y y dos aristas y , los conjuntos y ambos son máximamente independientes. El conjunto es independiente, pero no es máximamente independiente, porque es un subconjunto del conjunto independiente más grande . En este mismo gráfico, las camarillas máximas son los conjuntos y .
Un MIS también es un conjunto dominante en el gráfico, y cada conjunto dominante que es independiente debe ser máximo independiente, por lo que los MIS también se denominan conjuntos dominantes independientes .
Un gráfico puede tener muchos MIS de tamaños muy diversos; [1] el MIS más grande, o posiblemente varios igualmente grandes, de un gráfico se denomina conjunto máximo independiente . Las gráficas en las que todos los conjuntos máximos independientes tienen el mismo tamaño se denominan gráficas bien cubiertas .
La frase "conjunto independiente máximo" también se utiliza para describir subconjuntos máximos de elementos independientes en estructuras matemáticas distintas de los gráficos y, en particular, en espacios vectoriales y matroides .
Hay dos problemas algorítmicos asociados con los MIS: encontrar un solo MIS en un gráfico determinado y enumerar todos los MIS en un gráfico determinado .
Definición
Para un gráfico , un conjunto independiente es un conjunto independiente máximo si para, se cumple una de las siguientes condiciones: [2]
- dónde denota los vecinos de
Lo anterior se puede reformular como un vértice que pertenece al conjunto independiente o tiene al menos un vértice vecino que pertenece al conjunto independiente. Como resultado, cada borde del gráfico tiene al menos un punto final que no está en. Sin embargo, no es cierto que cada borde del gráfico tenga al menos uno, o incluso un punto final en
Observe que cualquier vecino de un vértice en el conjunto independiente no puede estar en porque estos vértices están separados por la definición del conjunto independiente.
Conjuntos de vértices relacionados
Si S es un conjunto independiente máximo en algún gráfico, es una camarilla máxima o un subgráfico completo máximo en el gráfico complementario . Una camarilla máxima es un conjunto de vértices que induce un subgrafo completo , y que no es un subconjunto de los vértices de ningún subgrafo completo más grande. Es decir, que es un conjunto S de tal manera que cada par de vértices en S está conectado por un borde y cada vértice no en S no se encuentra un borde de al menos un vértice en S . Un gráfico puede tener muchas camarillas máximas, de diferentes tamaños; encontrar el mayor de estos es el problema de la camarilla máxima .
Algunos autores incluyen la máxima como parte de la definición de camarilla y se refieren a las camarillas máximas simplemente como camarillas.
El complemento de un conjunto independiente máximo, es decir, el conjunto de vértices que no pertenecen al conjunto independiente, forma una cobertura de vértice mínima . Es decir, el complemento es una cobertura de vértice , un conjunto de vértices que incluye al menos un punto final de cada arista, y es mínimo en el sentido de que ninguno de sus vértices puede eliminarse conservando la propiedad de que es una cobertura. Las cubiertas de vértices mínimas se han estudiado en mecánica estadística en relación con el modelo de gas de celosía de esfera dura , una abstracción matemática de las transiciones de estado fluido-sólido. [3]
Todo conjunto independiente máximo es un conjunto dominante , un conjunto de vértices tal que cada vértice del gráfico pertenece al conjunto o es adyacente al conjunto. Un conjunto de vértices es un conjunto independiente máximo si y solo si es un conjunto dominante independiente.
Caracterizaciones de familias de grafos
Ciertas familias de gráficos también se han caracterizado en términos de sus camarillas máximas o conjuntos independientes máximos. Los ejemplos incluyen los gráficos irreductibles de la camarilla máxima y los gráficos irreductibles de la camarilla máxima hereditaria. Se dice que una gráfica es irreductible de camarilla máxima si cada camarilla máxima tiene una ventaja que no pertenece a ninguna otra camarilla máxima, y que la camarilla máxima hereditaria es irreducible si la misma propiedad es verdadera para cada subgrafo inducido. [4] hereditaria maximal-clique gráficos irreducibles incluyen gráficos libre de triángulo , gráficos bipartitos , y grafo de intervalos .
Las cografías se pueden caracterizar como gráficas en las que cada camarilla máxima se cruza con cada conjunto independiente máximo, y en las que la misma propiedad es verdadera en todas las subgrafías inducidas.
Delimitando el número de conjuntos
Moon y Moser (1965) demostraron que cualquier gráfico con n vértices tiene como máximo 3 n / 3 camarillas máximas. De manera complementaria, cualquier gráfico con n vértices también tiene como máximo 3 n / 3 conjuntos independientes máximos. Una gráfica con exactamente 3 n / 3 conjuntos independientes máximos es fácil de construir: simplemente tome la unión disjunta de n / 3 gráficas triangulares . Cualquier conjunto independiente máximo en este gráfico se forma eligiendo un vértice de cada triángulo. El gráfico complementario, con exactamente 3 n / 3 camarillas máximas, es un tipo especial de gráfico de Turán ; debido a su conexión con la Luna y el límite de Moser, estos gráficos también se denominan a veces gráficos Moon-Moser. Los límites más estrechos son posibles si se limita el tamaño de los conjuntos independientes máximos: el número de conjuntos independientes máximos de tamaño k en cualquier gráfico de n -vértices es como máximo
Las gráficas que logran este límite son nuevamente gráficas de Turán. [5]
Ciertas familias de gráficos pueden, sin embargo, tener límites mucho más restrictivos en el número de conjuntos independientes máximos o camarillas máximas. Si todos los gráficos de n -vértices en una familia de gráficos tienen O ( n ) aristas, y si cada subgráfico de un gráfico de la familia también pertenece a la familia, entonces cada gráfico de la familia puede tener como máximo O ( n ) camarillas máximas. , todos los cuales tienen tamaño O (1). [6] Por ejemplo, estas condiciones son verdaderas para los gráficos planos : cada gráfico plano de n -vértices tiene como máximo 3 n - 6 aristas, y un subgráfico de un gráfico plano es siempre plano, de lo cual se deduce que cada gráfico plano tiene O ( n ) camarillas máximas (de un tamaño máximo de cuatro). Las gráficas de intervalos y las gráficas cordales también tienen como máximo n camarillas máximas, aunque no siempre son gráficas dispersas .
El número de conjuntos independientes máximos en los gráficos de ciclo de n - vértices viene dado por los números de Perrin , y el número de conjuntos independientes máximos en los gráficos de trayectoria de n - vértices viene dado por la secuencia de Padovan . [7] Por lo tanto, ambos números son proporcionales a potencias de 1.324718, el número plástico .
Encontrar un único conjunto independiente máximo
Algoritmo secuencial
Dado un gráfico G (V, E), es fácil encontrar un solo MIS utilizando el siguiente algoritmo:
- Inicialice I a un conjunto vacío.
- Mientras V no está vacío:
- Elija un nodo v∈V;
- Agregue v al conjunto I;
- Quite de V el nodo v y todos sus vecinos.
- Regresar I.
El tiempo de ejecución es O ( m ) ya que en el peor de los casos tenemos que comprobar todos los bordes.
O (m) es obviamente el mejor tiempo de ejecución posible para un algoritmo en serie. Pero un algoritmo paralelo puede resolver el problema mucho más rápido.
Algoritmo paralelo de selección aleatoria [Algoritmo de Luby]
El siguiente algoritmo encuentra un MIS en el tiempo O (log n ). [2] [8] [9]
- Inicialice I a un conjunto vacío.
- Mientras V no está vacío:
- Elija un conjunto aleatorio de vértices S ⊆ V, seleccionando cada vértice v independientemente con probabilidad 1 / (2d (v)), donde d es el grado de v (el número de vecinos de v).
- Para cada borde en E, si sus dos extremos están en el conjunto aleatorio S, entonces elimine de S el extremo cuyo grado es menor (es decir, tiene menos vecinos). Romper los lazos arbitrariamente, por ejemplo, utilizando un orden lexicográfico en los nombres de los vértices.
- Agregue el conjunto S a I.
- Quite de V el conjunto S y todos los vecinos de los nodos en S.
- Regresar I.
ANÁLISIS : Para cada nodo v, divida sus vecinos en vecinos inferiores (cuyo grado es menor que el grado de v) y vecinos superiores (cuyo grado es mayor que el grado de v), rompiendo los lazos como en el algoritmo.
Llame a un nodo v bad si más de 2/3 de sus vecinos son vecinos superiores. Llame a un borde incorrecto si ambos extremos son incorrectos; de lo contrario, el borde es bueno .
- Al menos la mitad de todos los bordes siempre son buenos. PRUEBA: Construya una versión dirigida de G dirigiendo cada borde al nodo con el grado más alto (rompiendo los lazos arbitrariamente). Entonces, para cada nodo defectuoso, el número de bordes salientes es más de 2 veces el número de bordes entrantes. Entonces, cada borde defectuoso, que ingresa a un nodo v, se puede emparejar con un conjunto distinto de dos bordes que salen del nodo v. Por lo tanto, el número total de bordes es al menos 2 veces el número de bordes defectuosos.
- Para todo buen nodo u, la probabilidad de que un vecino de u sea seleccionado para S es al menos una cierta constante positiva. PRUEBA: la probabilidad de que NINGÚN vecino de u sea seleccionado para S es como máximo la probabilidad de que ninguno de los vecinos inferiores de u sea seleccionado. Para cada vecino inferior v, la probabilidad de que no se seleccione es (1-1 / 2d (v)), que es como máximo (1-1 / 2d (u)) (ya que d (u)> d (v )). El número de estos vecinos es al menos d (u) / 3, ya que u es bueno. Por tanto, la probabilidad de que no se seleccione ningún vecino inferior es como máximo 1-exp (-1/6).
- Para cada nodo u que se selecciona para S, la probabilidad de que u se elimine de S es como máximo 1/2. PRUEBA: Esta probabilidad es como máximo la probabilidad de que se seleccione un vecino superior de u a S. Para cada vecino superior v, la probabilidad de que se seleccione es como máximo 1 / 2d (v), que es como máximo 1 / 2d (u) (ya que d (v)> d (u)). Por límite de unión, la probabilidad de que no se seleccione ningún vecino superior es como máximo d (u) / 2d (u) = 1/2.
- Por tanto, para todo nodo bueno u, la probabilidad de que un vecino de u sea seleccionado para S y permanezca en S es una cierta constante positiva. Por tanto, la probabilidad de que se elimine u, en cada paso, es al menos una constante positiva.
- Por tanto, para cada borde bueno e, la probabilidad de que e se elimine, en cada paso, es al menos una constante positiva. Por lo tanto, el número de bordes buenos se reduce al menos en un factor constante en cada paso.
- Dado que al menos la mitad de los bordes son buenos, el número total de bordes también se reduce en un factor constante en cada paso.
- Por tanto, el número de pasos es O (log m ), donde m es el número de aristas. Esto está limitado por.
Un gráfico del peor de los casos, en el que el número medio de pasos es , es un gráfico formado por n / 2 componentes conectados, cada uno con 2 nodos. El grado de todos los nodos es 1, por lo que cada nodo se selecciona con probabilidad 1/2 y con probabilidad 1/4 no se eligen ambos nodos de un componente. Por lo tanto, el número de nodos se reduce en un factor de 4 en cada paso, y el número esperado de pasos es.
Algoritmo paralelo de prioridad aleatoria
El siguiente algoritmo es mejor que el anterior porque siempre se agrega al menos un nuevo nodo en cada componente conectado: [10] [9]
- Inicialice I a un conjunto vacío.
- Si bien V no está vacío, cada nodo v hace lo siguiente:
- Selecciona un número aleatorio r (v) en [0,1] y lo envía a sus vecinos;
- Si r (v) es menor que los números de todos los vecinos de v, entonces v se inserta en I, se elimina de V y les dice a sus vecinos acerca de esto;
- Si v escuchó que uno de sus vecinos entró en I, entonces v se elimina de V.
- Regresar I.
Tenga en cuenta que en cada paso, el nodo con el número más pequeño en cada componente conectado siempre ingresa I, por lo que siempre hay algún progreso. En particular, en el peor de los casos del algoritmo anterior ( n / 2 componentes conectados con 2 nodos cada uno), se encontrará un MIS en un solo paso.
ANÁLISIS :
- Un nodo tiene probabilidad al menos de ser removido. PRUEBA: Para cada borde que conecta un par de nodos, reemplácelo con dos bordes dirigidos, uno de y el otro . Darse cuenta deahora es el doble de grande. Por cada par de bordes dirigidos, define dos eventos: y , elimina preventivamente y elimina preventivamente , respectivamente. El evento ocurre cuando y , dónde es vecino de y es vecino . Recuerde que a cada nodo se le asigna un número aleatorio en el mismo rango [0, 1]. En un ejemplo simple con dos nodos separados, cada uno tiene probabilidadde ser el más pequeño. Si hay tres nodos disjuntos, cada uno tiene probabilidadde ser el más pequeño. En el caso de, tiene probabilidad al menos de ser el más pequeño porque es posible que un vecino de es también el vecino de , por lo que un nodo se contabiliza dos veces. Usando la misma lógica, el evento también tiene probabilidad al menos de ser removido.
- Cuando los eventos y ocurren, eliminan y bordes salientes dirigidos, respectivamente. PRUEBA: En caso de, Cuándo se elimina, todos los nodos vecinos también se eliminan. El número de bordes dirigidos salientes desde eliminado es . Con la misma lógica elimina bordes salientes dirigidos.
- En cada iteración del paso 2, se espera que se eliminen la mitad de los bordes. PRUEBA: Si el evento sucede entonces todos los vecinos de son removidos; por lo tanto, el número esperado de bordes eliminados debido a este evento es al menos. Lo mismo es cierto para el evento inverso, es decir, el número esperado de bordes eliminados es al menos . Por lo tanto, para cada borde no dirigido, el número esperado de bordes eliminados debido a que uno de estos nodos tiene el valor más pequeño es . Sumando todos los bordes,, da un número esperado de bordes eliminados en cada paso, pero cada borde se cuenta dos veces (una vez por dirección), lo que da Bordes eliminados a la espera de cada paso.
- Por tanto, el tiempo de ejecución esperado del algoritmo es cual es . [9]
Algoritmo paralelo de permutación aleatoria [Algoritmo de Blelloch]
En lugar de aleatorizar en cada paso, es posible aleatorizar una vez, al comienzo del algoritmo, fijando un orden aleatorio en los nodos. Dado este orden fijo, el siguiente algoritmo paralelo logra exactamente el mismo MIS que el algoritmo #Sequential (es decir, el resultado es determinista): [11]
- Inicialice I a un conjunto vacío.
- Mientras V no está vacío:
- Sea W el conjunto de vértices en V sin vecinos anteriores (basado en el orden fijo);
- Agregue W a I;
- Quite de V los nodos del conjunto W y todos sus vecinos.
- Regresar I.
Entre los algoritmos totalmente secuenciales y totalmente paralelos, existe un continuo de algoritmos que son en parte secuenciales y en parte paralelos. Dado un orden fijo en los nodos y un factor δ∈ (0,1], el siguiente algoritmo devuelve el mismo MIS:
- Inicialice I a un conjunto vacío.
- Mientras V no está vacío:
- Seleccione un factor δ∈ (0,1].
- Sea P el conjunto de δ n nodos que están primeros en el orden fijo.
- Sea W un MIS en P usando el algoritmo totalmente paralelo.
- Agregue W a I;
- Quite de V todos los nodos del prefijo P y todos los vecinos de los nodos del conjunto W.
- Regresar I.
Establecer δ = 1 / n da el algoritmo totalmente secuencial; al establecer δ = 1 se obtiene el algoritmo totalmente paralelo.
ANÁLISIS : Con una selección adecuada del parámetro δ en el algoritmo parcialmente paralelo, es posible garantizar que finalice después de como máximo log (n) llamadas al algoritmo completamente paralelo, y el número de pasos en cada llamada es como máximo log (norte). Por tanto, el tiempo de ejecución total del algoritmo parcialmente paralelo es. Por lo tanto, el tiempo de ejecución del algoritmo completamente paralelo también es como máximo. Los principales pasos de prueba son:
- Si en el paso i seleccionamos, Donde D es el grado máximo de un nodo en el gráfico, entonces WHP todos los nodos restantes después de la etapa i tienen un grado en la mayoría. Por lo tanto, después de los pasos log ( D ), todos los nodos restantes tienen grado 0 (desde D < n ) y se pueden eliminar en un solo paso.
- Si, en cualquier paso, el grado de cada nodo es como máximo d , y seleccionamos(para cualquier constante C ), entonces WHP el camino más largo en el gráfico dirigido determinado por el orden fijo tiene longitud. Por lo tanto, el algoritmo completamente paralelo toma como máximo pasos (dado que la ruta más larga es un límite en el peor de los casos en el número de pasos en ese algoritmo).
- La combinación de estos dos hechos da que, si seleccionamos , entonces WHP el tiempo de ejecución del algoritmo parcialmente paralelo es .
Listado de todos los conjuntos independientes máximos
Un algoritmo para enumerar todos los conjuntos independientes máximos o camarillas máximas en un gráfico se puede utilizar como subrutina para resolver muchos problemas de gráficos NP-completos. De manera más obvia, las soluciones al problema del conjunto máximo independiente, el problema de la camarilla máxima y el problema dominante mínimo independiente deben ser todos conjuntos independientes máximos o camarillas máximas, y se pueden encontrar mediante un algoritmo que enumere todos los conjuntos independientes máximos o camarillas máximas y retiene los de mayor o menor tamaño. De manera similar, la cobertura de vértice mínima se puede encontrar como el complemento de uno de los conjuntos independientes máximos. Lawler (1976) observó que la lista de conjuntos máximos independientes también se puede utilizar para hallar gráficas de tres colores: una gráfica puede tener tres colores si y sólo si el complemento de uno de sus conjuntos máximos independientes es bipartito . Usó este enfoque no solo para la coloración en 3, sino como parte de un algoritmo de coloración de gráficos más general, y desde entonces otros autores han perfeccionado enfoques similares para la coloración de gráficos. [12] Otros problemas más complejos también pueden modelarse como encontrar una camarilla o un conjunto independiente de un tipo específico. Esto motiva el problema algorítmico de enumerar todos los conjuntos independientes máximos (o, de manera equivalente, todas las camarillas máximas) de manera eficiente.
Es sencillo convertir una prueba del límite de 3 n / 3 de Moon y Moser en el número de conjuntos independientes máximos en un algoritmo que enumere todos esos conjuntos en el tiempo O (3 n / 3 ). [13] Para gráficos que tienen el mayor número posible de conjuntos independientes máximos, este algoritmo toma un tiempo constante por conjunto de salida. Sin embargo, un algoritmo con este límite de tiempo puede ser muy ineficaz para gráficos con un número más limitado de conjuntos independientes. Por esta razón, muchos investigadores han estudiado algoritmos que enumeran todos los conjuntos independientes máximos en tiempo polinómico por conjunto de salida. [14] El tiempo por conjunto máximo independiente es proporcional al de la multiplicación de matrices en gráficos densos, o más rápido en varias clases de gráficos dispersos. [15]
Paralelización de la búsqueda de conjuntos máximos independientes
Historia
El problema del conjunto independiente máximo originalmente se pensó que no era trivial para paralelizar debido al hecho de que el conjunto independiente máximo lexicográfico resultó ser P-Completo ; Sin embargo, se ha demostrado que una solución paralela determinista podría estar dada por unreducción del empaque de ajuste máximo o del problema de emparejamiento máximo o por unreducción del problema de 2-satisfacibilidad . [16] [17] Normalmente, la estructura del algoritmo proporcionado sigue otros algoritmos de gráficos paralelos, es decir, subdividen el gráfico en problemas locales más pequeños que se pueden resolver en paralelo ejecutando un algoritmo idéntico.
La investigación inicial sobre el problema del conjunto independiente máximo comenzó en el modelo PRAM y desde entonces se ha expandido para producir resultados para algoritmos distribuidos en clústeres de computadoras . Los muchos desafíos del diseño de algoritmos distribuidos en paralelo se aplican al mismo nivel que el problema del conjunto máximo independiente. En particular, encontrar un algoritmo que exhiba un tiempo de ejecución eficiente y sea óptimo en la comunicación de datos para subdividir el gráfico y fusionar el conjunto independiente.
Clase de complejidad
Fue mostrado en 1984 por Karp et al. que una solución paralela determinista en PRAM al conjunto independiente máximo pertenecía al zoológico de complejidad de la clase de Nick de. [18] Es decir, su algoritmo encuentra un conjunto independiente máximo en utilizando , dónde es el tamaño del conjunto de vértices. En el mismo documento, también se proporcionó una solución paralela aleatoria con un tiempo de ejecución de utilizando procesadores. Poco después, Luby y Alon et al. mejoró de forma independiente este resultado, llevando el problema del conjunto independiente máximo al ámbito de con un tiempo de ejecución usando procesadores, donde es el número de aristas del gráfico. [17] [8] [19] Para mostrar que su algoritmo está en, inicialmente presentaron un algoritmo aleatorio que utiliza procesadores, pero podría ser desaleatorizado con un adicional procesadores. Hoy en día, sigue siendo una pregunta abierta si el problema del conjunto independiente máximo está en.
Comunicación e intercambio de datos
Los algoritmos de conjuntos independientes máximos distribuidos están fuertemente influenciados por algoritmos en el modelo PRAM. El trabajo original de Luby y Alon et al. ha dado lugar a varios algoritmos distribuidos. [20] [21] [22] [19] En términos de intercambio de bits, estos algoritmos tenían un límite inferior de tamaño de mensaje por ronda debits y requeriría características adicionales del gráfico. Por ejemplo, sería necesario conocer el tamaño del gráfico o se podría consultar el grado máximo de vértices vecinos para un vértice dado. En 2010, Métivier et al. redujo el tamaño de mensaje requerido por ronda a, que es óptimo y eliminó la necesidad de conocimientos gráficos adicionales. [23]
Notas
- ↑ Erdős (1966) muestra que el número de diferentes tamaños de MIS en ungráfico de n -vértices puede ser tan grande como n - log n - O (log log n ) y nunca es mayor que n - log n .
- ^ a b Algoritmo de Luby, en: Lecture Notes for Randomized Algorithms, Última actualización por Eric Vigoda el 2 de febrero de 2006
- ^ Weigt y Hartmann (2001) .
- ^ Sistema de información sobre inclusiones de clases de gráficos: gráficos irreductibles de camarilla máxima Archivado el 9 de julio de 2007 en la Wayback Machine y gráficos irreductibles de la camarilla máxima hereditaria Archivado 08/07/2007 en la Wayback Machine .
- ^ Byskov (2003) . Para obtener resultados anteriores relacionados, consulte Croitoru (1979) y Eppstein (2003) .
- ^ Chiba y Nishizeki (1985) . Chiba y Nishizeki expresan la condición de tenerbordesO ( n ) de manera equivalente, en términos de que la arboricidad de las gráficas en la familia es constante.
- ^ Bisdorff y Marichal (2007) ; Euler (2005) ; Füredi (1987) .
- ↑ a b Luby, M. (1986). "Un algoritmo paralelo simple para el problema de conjunto independiente máximo". Revista SIAM de Computación . 15 (4): 1036–1053. CiteSeerX 10.1.1.225.5475 . doi : 10.1137 / 0215074 .
- ^ a b c "Principios de la Computación Distribuida (lección 7)" (PDF) . ETH Zurich. Archivado desde el original (PDF) el 21 de febrero de 2015 . Consultado el 21 de febrero de 2015 .
- ^ Métivier, Y .; Robson, JM; Saheb-Djahromi, N .; Zemmari, A. (2010). "Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima". Computación distribuida . 23 (5–6): 331. doi : 10.1007 / s00446-010-0121-5 . S2CID 36720853 .
- ^ Blelloch, Guy; Fineman, Jeremy; Shun, Julian (2012). "El conjunto independiente máximo secuencial codicioso y el emparejamiento son paralelos en promedio". arXiv : 1202,3205 [ cs.DS ].
- ^ Eppstein (2003) ; Byskov (2003) .
- ^ Eppstein (2003) . Para un límite de coincidencia para el algoritmo Bron-Kerbosch ampliamente utilizado, consulte Tomita, Tanaka y Takahashi (2006) .
- ^ Bomze y col. (1999) ; Eppstein (2005) ; Jennings y Motycková (1992) ; Johnson, Yannakakis y Papadimitriou (1988) ; Lawler, Lenstra y Rinnooy Kan (1980) ; Liang, Dhall y Lakshmivarahan (1991) ; Makino y Uno (2004) ; Mishra y Pitt (1997) ; Stix (2004) ; Tsukiyama y col. (1977) ; Yu y Chen (1993) .
- ^ Makino y Uno (2004) ; Eppstein (2005) .
- ^ Cook, Stephen (junio de 1983). "Una descripción general de la complejidad computacional" (PDF) . Comun. ACM . 26 (6): 400–408. doi : 10.1145 / 358141.358144 . S2CID 14323396 . Archivado desde el original (PDF) el 4 de marzo de 2016.
- ^ a b Barba, Luis (octubre de 2012). "REVISIÓN DE LITERATURA: Algoritmos paralelos para el problema de conjunto independiente máximo en gráficos" (PDF) .
- ^ Karp, RM; Wigderson, A. (1984). "Un algoritmo paralelo rápido para el problema del conjunto independiente máximo". Proc. 16º Simposio ACM de Teoría de la Computación .
- ^ a b Alon, Noga; Laszlo, Babai; Alon, Itai (1986). "Un algoritmo paralelo aleatorio rápido y simple para el problema del conjunto independiente máximo". Revista de algoritmos . 7 (4): 567–583. doi : 10.1016 / 0196-6774 (86) 90019-2 .
- ^ Peleg, David (2000). Computación distribuida: un enfoque sensible a la localidad . doi : 10.1137 / 1.9780898719772 . ISBN 978-0-89871-464-7.
- ^ Lynch, NA (1996). "Algoritmos distribuidos". Morgan Kaufmann .
- ^ Wattenhofer, R. "Capítulo 4: Conjunto independiente máximo" (PDF) .
- ^ Métivier, Y .; Robson, JM; Saheb-Djahromi, N .; Zemmari, A. (2010). "Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima". Computación distribuida .
Referencias
- Bisdorff, R .; Marichal, J.-L. (2007), Contando conjuntos independientes máximos no isomórficos del gráfico de n ciclos , arXiv : math.CO/0701647.
- Bomze, MI; Budinich, M .; Pardalos, PM; Pelillo, M. (1999), "El problema de la camarilla máxima", Manual de optimización combinatoria , 4 , Kluwer Academic Publishers, págs. 1-74, CiteSeerX 10.1.1.48.4074.
- Byskov, JM (2003), "Algoritmos para k- colorear y encontrar conjuntos independientes máximos", Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos , Soda '03, págs. 456–457, ISBN 9780898715385.
- Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph Listing algoritmos" , SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137 / 0214017 , S2CID 207051803.
- Croitoru, C. (1979), "Sobre establos en gráficos", Proc. Tercer Coll. Investigación operativa , Universidad Babeş-Bolyai , Cluj-Napoca, Rumania, págs. 55–60.
- Eppstein, D. (2003), "Pequeños conjuntos máximos independientes y coloración gráfica exacta más rápida" (PDF) , Journal of Graph Algorithms and Applications , 7 (2): 131–140, arXiv : cs.DS / 0011009 , CiteSeerX 10.1. 1.342.4049 , doi : 10.7155 / jgaa.00064.
- Eppstein, D. (2005), "Todos los conjuntos independientes máximos y dominancia dinámica para gráficos dispersos", Proc. Decimosexto Simposio anual ACM-SIAM sobre algoritmos discretos , 5 , págs. 451–459, arXiv : cs.DS / 0407036 , doi : 10.1145 / 1597036.1597042 , S2CID 2769046.
- Erdős, P. (1966), "Sobre camarillas en gráficos", Israel J. Math. , 4 (4): 233–234, doi : 10.1007 / BF02771637 , MR 0205874 , S2CID 121993028.
- Euler, R. (2005), "El número de Fibonacci de un gráfico de cuadrícula y una nueva clase de secuencias enteras", Journal of Integer Sequences , 8 (2): 05.2.6, Bibcode : 2005JIntS ... 8 ... 26E.
- Füredi, Z. (1987), "El número de conjuntos independientes máximos en gráficos conectados", Journal of Graph Theory , 11 (4): 463–470, doi : 10.1002 / jgt.3190110403.
- Jennings, E .; Motycková, L. (1992), "Un algoritmo distribuido para encontrar todas las camarillas máximas en un gráfico de red", Proc. Primer Simposio Latinoamericano de Informática Teórica , Lecture Notes in Computer Science, 583 , Springer-Verlag, págs. 281–293
- Johnson, DS ; Yannakakis, M .; Papadimitriou, CH (1988), "Sobre la generación de todos los conjuntos independientes máximos", Information Processing Letters , 27 (3): 119-123, doi : 10.1016 / 0020-0190 (88) 90065-8.
- Lawler, EL (1976), "Una nota sobre la complejidad del problema de los números cromáticos", Information Processing Letters , 5 (3): 66–67, doi : 10.1016 / 0020-0190 (76) 90065-X.
- Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG (1980), "Generación de todos los conjuntos independientes máximos: algoritmos de dureza NP y tiempo polinomial" (PDF) , SIAM Journal on Computing , 9 (3): 558–565, doi : 10.1137 / 0209042.
- Leung, JY-T. (1984), "Algoritmos rápidos para generar todos los conjuntos máximos independientes de intervalos, arco circular y gráficos cordales", Journal of Algorithms , 5 : 22–35, doi : 10.1016 / 0196-6774 (84) 90037-3.
- Liang, YD; Dhall, SK; Lakshmivarahan, S. (1991), Sobre el problema de encontrar todos los conjuntos independientes del peso máximo en gráficas de arco circular y de intervalo , págs. 465–470 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - Makino, K .; Uno, T. (2004), "Nuevos algoritmos para enumerar todas las camarillas máximas", Teoría de algoritmos - SWAT 2004 , Lecture Notes in Compute Science, 3111 , Springer-Verlag, pp. 260-272, CiteSeerX 10.1.1.138.705 , doi : 10.1007 / 978-3-540-27810-8_23 , ISBN 978-3-540-22339-9 Parámetro desconocido
|book-title=
ignorado ( ayuda ) . ISBN 9783540223399 , 9783540278108 . - Mishra, N .; Pitt, L. (1997), "Generación de todos los conjuntos máximos independientes de hipergráficos de grado acotado", Proc. Décima Conf. Teoría del aprendizaje computacional , págs. 211-217, doi : 10.1145 / 267460.267500 , ISBN 978-0-89791-891-6, S2CID 5254186.
- Luna, JW; Moser, L. (1965), "Sobre camarillas en gráficos", Israel Journal of Mathematics , 3 : 23-28, doi : 10.1007 / BF02760024 , MR 0182577 , S2CID 9855414.
- Stix, V. (2004), "Encontrar todas las camarillas máximas en gráficos dinámicos", Aplicación de optimización computacional. , 27 (2): 173–186, CiteSeerX 10.1.1.497.6424 , doi : 10.1023 / B: COAP.0000008651.28952.b6 , S2CID 17824282
- Tomita, E .; Tanaka, A .; Takahashi, H. (2006), "La complejidad de tiempo en el peor de los casos para generar todas las camarillas máximas y experimentos computacionales", Informática teórica , 363 (1): 28–42, doi : 10.1016 / j.tcs.2006.06.015.
- Tsukiyama, S .; Ide, M .; Ariyoshi, H .; Shirakawa, I. (1977), "Un nuevo algoritmo para generar todos los conjuntos independientes máximos", SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137 / 0206036.
- Weigt, Martin; Hartmann, Alexander K. (2001), "Cubiertas de vértices mínimos en gráficos aleatorios de conectividad finita: una imagen de gas reticular de esfera dura", Phys. Rev. E , 63 (5): 056127, arXiv : cond-mat / 0011446 , Bibcode : 2001PhRvE..63e6127W , doi : 10.1103 / PhysRevE.63.056127 , PMID 11414981 , S2CID 16773685.
- Yu, C.-W .; Chen, G.-H. (1993), "Generar todos los conjuntos independientes máximos en gráficos de permutación", Internat. J. Comput. Matemáticas. , 47 (1–2): 1–8, doi : 10.1080 / 00207169308804157.