Primer algoritmo recursivo más grande

Algoritmo para colorear gráficos.

El algoritmo recursivo más grande primero ( RLF ) es una heurística para el problema de coloración de gráficos NP-hard . Fue propuesto originalmente por Frank Leighton en 1979. ^[1]

El algoritmo RLF asigna colores a los vértices de un gráfico construyendo cada clase de color de una en una. Para ello, identifica un conjunto máximo independiente de vértices en el gráfico, les asigna el mismo color y luego los elimina del gráfico. Estas acciones se repiten en el subgrafo restante hasta que no queden vértices.

Para formar soluciones de alta calidad (soluciones que utilizan pocos colores), el algoritmo RLF utiliza reglas heurísticas especializadas para intentar identificar conjuntos independientes de "buena calidad". Estas heurísticas hacen que el algoritmo RLF sea exacto para gráficos bipartitos , de ciclo y de rueda . ^{[2] Sin embargo, en general, el algoritmo es aproximado y bien puede devolver soluciones que utilizan más colores que el} número cromático del gráfico .

Descripción

El algoritmo se puede describir mediante los siguientes tres pasos. Al final de este proceso, se obtiene una partición de los vértices que representan una coloración factible del gráfico . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle |{\mathcal {S}}|}$ ${\displaystyle G}$

1. Sea una solución vacía. Además, sea el gráfico que deseamos colorear, que comprende un conjunto de vértices y un conjunto de aristas . ${\displaystyle {\mathcal {S}}=\emptyset }$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$
2. Identificar un conjunto independiente máximo . Para hacer esto: ${\displaystyle S\subseteq V}$
   1. El primer vértice agregado debe ser el vértice que tiene el mayor número de vecinos. ${\displaystyle S}$ ${\displaystyle G}$
   2. Los vértices posteriores agregados deben elegirse como aquellos que (a) no son actualmente adyacentes a ningún vértice en y (b) tienen un número máximo de vecinos que son adyacentes a los vértices en . Los empates en la condición (b) se pueden romper seleccionando el vértice con el número mínimo de vecinos que no están en . Los vértices se van añadiendo de esta manera hasta que sea imposible añadir más vértices. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$
3. Ahora establece y elimina los vértices de from . Si todavía contiene vértices, regrese al Paso 2; de lo contrario terminará. ${\displaystyle {\mathcal {S}}={\mathcal {S}}\cup \{S\}}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle G}$

Ejemplo

Un gráfico de rueda con siete vértices.

Considere el gráfico que se muestra a la derecha. Este es un gráfico de rueda y, por lo tanto, RLF lo coloreará de manera óptima. La ejecución del algoritmo da como resultado que los vértices se seleccionen y coloreen en el siguiente orden: ${\displaystyle G=(V,E)}$

1. Vértice (color 1) ${\displaystyle g}$
2. Vértice , y luego (color 2) ${\displaystyle a}$ ${\displaystyle c}$ ${\displaystyle e}$
3. Vértice , y luego (color 3) ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle f}$

Esto da la solución final de tres colores . ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

Actuación

Sea el número de vértices del gráfico y sea el número de aristas. Usando notación O grande , en su publicación original Leighton afirma que la complejidad de RLF es ; sin embargo, esto se puede mejorar. Gran parte del coste de este algoritmo se debe al Paso 2, donde la selección de vértices se realiza de acuerdo con las reglas heurísticas establecidas anteriormente. De hecho, cada vez que se selecciona un vértice para agregarlo al conjunto independiente , es necesario volver a calcular la información sobre los vecinos para cada vértice sin color. Estos cálculos se pueden realizar a tiempo, lo que significa que la complejidad general de RLF es . ^[2] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {O}}(m)}$ ${\displaystyle {\mathcal {O}}(mn)}$

Si la heurística del Paso 2 se reemplaza con selección aleatoria, entonces la complejidad de este algoritmo se reduce a ; sin embargo, el algoritmo resultante normalmente devolverá soluciones de menor calidad en comparación con las de RLF. ^[2] Ahora también será inexacto para los gráficos bipartitos , de ciclo y de rueda . ${\displaystyle {\mathcal {O}}(n+m)}$

En una comparación empírica realizada por Lewis en 2021, se demostró que RLF produce coloraciones de vértices significativamente mejores que heurísticas alternativas como el algoritmo codicioso y el algoritmo DSatur en gráficos aleatorios . Sin embargo, también se consideró que los tiempos de ejecución con RLF eran mayores que estas alternativas debido a su mayor complejidad general. ^[2] ${\displaystyle {\mathcal {O}}(n+m)}$ ${\displaystyle {\mathcal {O}}((n+m)\lg n)}$

Referencias

1. Leighton, F. (1979). "Un algoritmo de coloración de gráficos para grandes problemas de programación". Revista de Investigación de la Oficina Nacional de Normas . 84 (6): 489–503. doi :10.6028/jres.084.024. PMC  6756213 . PMID  34880531.
2. Lewis, R. (2021). Una guía para colorear gráficos: algoritmos y aplicaciones . Textos en Informática. Saltador. doi :10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. S2CID  57188465.

enlaces externos

• Algoritmos de coloración de gráficos de alto rendimiento Conjunto de algoritmos de coloración de gráficos (implementados en C++) utilizados en el libro Una guía para la coloración de gráficos: algoritmos y aplicaciones (Springer International Publishers, 2021).