Algoritmo MaxCliqueDyn

El algoritmo MaxCliqueDyn es un algoritmo para encontrar una camarilla máxima en un grafo no dirigido.

MaxCliqueDyn se basa en el algoritmo MaxClique, que encuentra una camarilla máxima de tamaño limitado. El límite se determina mediante un algoritmo de coloración . MaxCliqueDyn extiende MaxClique para incluir límites que varían dinámicamente.

Este algoritmo fue diseñado por Janez Konc y su descripción se publicó en 2007. ^{[ 1 ]} En comparación con algoritmos anteriores, MaxCliqueDyn tiene un algoritmo de coloración mejorado (ColorSort) y aplica límites superiores más estrictos y computacionalmente más costosos en una fracción del espacio de búsqueda. ^{[ 1 ]} Ambas mejoras reducen el tiempo para encontrar la clique máxima. Además de reducir el tiempo, el algoritmo de coloración mejorado también reduce el número de pasos necesarios para encontrar una clique máxima.

Algoritmo MaxClique

El algoritmo MaxClique ^{[ 2 ]} es el algoritmo básico a partir del cual se extiende MaxCliqueDyn. El pseudocódigo del algoritmo es:

procedimiento MaxClique(R, C) es Q = Ø, Q _max = Ø mientras R ≠ Ø hacer elige un vértice p con un color máximo C(p) del conjunto R R := R\{p} si |Q| + C(p)>|Q _max | entonces Q := Q ⋃ {p} si R ⋂ Γ(p) ≠ Ø entonces obtener una coloración de vértices C' de G(R ⋂ Γ(p)) MaxClique(R ⋂ Γ(p), C') de lo contrario si |Q|>|Q _max | entonces Q _max := Q Q := Q\{p} de lo contrario , regresar fin mientras

donde Q es un conjunto de vértices de la camarilla en crecimiento actual, Q _max es un conjunto de vértices de la camarilla más grande encontrada hasta el momento, R es un conjunto de vértices candidatos, Γ(p) es el conjunto de todos los vértices adyacentes a p, y C su conjunto correspondiente de clases de color. El algoritmo MaxClique busca recursivamente una camarilla máxima agregando y eliminando vértices de Q.

Algoritmos de coloración

Algoritmo de coloración aproximada

MaxClique utiliza un algoritmo de coloración aproximada ^{[ 2 ]} para obtener un conjunto de clases de color C. En el algoritmo de coloración aproximada, los vértices se colorean uno por uno en el mismo orden en que aparecen en un conjunto de vértices candidatos R , de modo que si el siguiente vértice p no es adyacente a todos los vértices de la misma clase de color, se agrega a esta clase, y si p es adyacente a al menos un vértice de cada una de las clases de color existentes, se coloca en una nueva clase de color.

El algoritmo MaxClique devuelve los vértices R ordenados por sus colores. Vértices $v\in R$ con colores $C(v)<{|Q_{max}|}-{|Q|}+1$ Nunca se añaden a la camarilla actual Q. Por lo tanto, ordenar esos vértices por color no es útil para el algoritmo MaxClique.

Clasificación por color

El algoritmo ColorSort mejora el algoritmo de coloración aproximada al tener en cuenta la observación anterior. A cada vértice se le asigna una clase de color. $C_{k}$ . Si $k<{|Q_{max}|}-{|Q|}+1$ , el vértice se mueve al conjunto R (detrás del último vértice en R ). Si $k\geq {|Q_{max}|}-{|Q|}+1$ , entonces el vértice permanece en $C_{k}$ y no se mueve a R. Al final, todos los vértices que quedan en $C_{k}$ (dónde $k\geq {|Q_{max}|}-{|Q|}+1$ ) se agregan al final de R tal como aparecen en cada $C_{k}$ y en orden creciente con respecto al índice $k$ En el algoritmo ColorSort, solo a estos vértices se les asignan colores. $C(v)=k$ .

El pseudocódigo del algoritmo ColorSort es: ^{[ 1 ]}

El procedimiento ColorSort(R, C) es max_no := 1; k _min := |Q _max | − |Q| + 1; Si k _min ≤ 0, entonces k _min := 1; j := 0; C ₁ := Ø; C ₂ := Ø; para i := 0 hasta |R| − 1 hacer p := R[i]; {el i-ésimo vértice en R} k := 1; mientras C _k ⋂ Γ(p) ≠ Ø hacer k := k+1; si k > max_no entonces max_no := k; C _{max_no+1} := Ø; fin si C _k := C _k ⋃ {p}; si k < k _minentonces R[j] := R[i]; j := j+1; fin si fin para C[j−1] := 0; para k := k _min hasta max_no hacer para i := 1 hasta |C _k | hacer R[j] := C _k [i]; C[j] := k; j := j+1; fin para fin para

Ejemplo

El gráfico anterior puede describirse como un conjunto candidato de vértices R = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ }, y utilizarse como entrada tanto para el algoritmo de coloración aproximada como para el algoritmo ColorSort. Cualquiera de los dos algoritmos puede utilizarse para construir la siguiente tabla:

El algoritmo de coloración aproximada devuelve el conjunto de vértices R = {7 ⁽⁵⁾ , 5 ⁽²⁾ , 1 ( ⁴⁾ , 6 ⁽³⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } y su correspondiente conjunto de clases de color C = {1,1,2,2,2,3,3,3}. El algoritmo ColorSort devuelve el conjunto de vértices R = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } y su correspondiente conjunto de clases de color C = {–,–,–,–,–,3,3,3}, donde – representa una clase de color desconocida con k < 3.

Algoritmo MaxCliqueDyn

El algoritmo MaxCliqueDyn extiende el algoritmo MaxClique utilizando el algoritmo ColorSort en lugar del algoritmo de coloración aproximada para determinar las clases de color. En cada paso de MaxClique, el algoritmo MaxCliqueDyn también recalcula los grados de los vértices en R con respecto al vértice en el que se encuentra actualmente el algoritmo. Estos vértices se ordenan luego en orden descendente con respecto a sus grados en el grafo G(R) . Posteriormente, el algoritmo ColorSort considera los vértices en R ordenados por sus grados en el grafo inducido G(R) en lugar de en G. De esta manera, el número de pasos necesarios para encontrar la clique máxima se reduce al mínimo. Aun así, el tiempo de ejecución total del algoritmo MaxClique no mejora, debido al costo computacional. $O(|R|^{2})$ La determinación de los grados y la ordenación de los vértices en R se mantiene igual.

El pseudocódigo del algoritmo MaxCliqueDyn es: ^{[ 1 ]}

El procedimiento MaxCliqueDyn(R, C, nivel) es S[nivel] := S[nivel] + S[nivel−1] − S _antiguo [nivel]; S _antiguo [nivel] := S[nivel−1]; mientras R ≠ Ø hacer elige un vértice p con C(p) máximo (último vértice) de R; R := R\{p}; Si |Q| + C[índice de p en R] > |Q _máx | entonces Q := Q ⋃ {p}; Si R ⋂ Γ(p) ≠ Ø entonces si S[nivel]/TODOS LOS PASOS < T _límiteentonces calcular los grados de los vértices en G(R ⋂ Γ(p)); ordenar los vértices en R ⋂ Γ(p) en orden descendente con respecto a sus títulos; fin si ColorSort(R ⋂ Γ(p), C') S[nivel] := S[nivel] + 1; TODOS LOS PASOS := TODOS LOS PASOS + 1; MaxCliqueDyn(R ⋂ Γ(p), C', nivel + 1); else if |Q| > |Q _max | then Q _max := Q; Q := Q\{p}; de lo contrario , regresar fin mientras

El valor _límiteT se puede determinar experimentando con gráficos aleatorios. En el artículo original se determinó que el algoritmo funciona mejor para T _límite = 0,025.

Referencias

1 2 3 4 Janez Konc; Dusanka Janezic (2007). "Un algoritmo de ramificación y acotación mejorado para el problema del clique máximo" (PDF) . MATCH Communications in Mathematical and in Computer Chemistry . 58 (3): 569– 590.Código fuente
1 2 Tomita, Etsuji; Seki, Tomokazu (2003). "Un algoritmo eficiente de ramificación y acotación para encontrar una camarilla máxima" (PDF) . En Calude, CS; Dinneen, MJ; Vajnovszki, V. (eds.). DMTCS 2003. LNCS. pp. 278–289 . Archivado del original (PDF) el 11 de septiembre de 2016. Véase también: E. Tomita; T. Seki (2007). "Un algoritmo eficiente de ramificación y acotación para encontrar una camarilla máxima". J Glob Optim . 37 : 95– 111. doi : 10.1007/s10898-006-9039-7 .

[Konc2007-1] 1 2 3 4 Janez Konc; Dusanka Janezic (2007). "Un algoritmo de ramificación y acotación mejorado para el problema del clique máximo" (PDF) . MATCH Communications in Mathematical and in Computer Chemistry . 58 (3): 569– 590.Código fuente

[Tomita2003-2] 1 2 Tomita, Etsuji; Seki, Tomokazu (2003). "Un algoritmo eficiente de ramificación y acotación para encontrar una camarilla máxima" (PDF) . En Calude, CS; Dinneen, MJ; Vajnovszki, V. (eds.). DMTCS 2003. LNCS. pp. 278–289 . Archivado del original (PDF) el 11 de septiembre de 2016. Véase también: E. Tomita; T. Seki (2007). "Un algoritmo eficiente de ramificación y acotación para encontrar una camarilla máxima". J Glob Optim . 37 : 95– 111. doi : 10.1007/s10898-006-9039-7 .

[ 1 ]

[ 2 ]