Evolución de Poblaciones de Subgrafos Resueltos con Cruce y Reparación de Restricciones

Área de la Ciencia:

• Ciencias de la Computación
• Teoría de Grafos
• Diseño de Algoritmos

Sus antecedentes:

• Los problemas de grafos parametrizados implican encontrar pequeños conjuntos de vértices que cumplan criterios específicos.
• Los métodos existentes pueden tener problemas de escalabilidad y eficiencia para estructuras de grafos complejas.

Objetivo del estudio:

• Desarrollar un enfoque novedoso basado en poblaciones para resolver problemas de grafos parametrizados.
• Introducir un operador de cruce alélico generalizado para combinar soluciones de subgrafos.
• Analizar la complejidad del tiempo de ejecución y la aplicabilidad práctica del método propuesto.

Principales métodos:

• Algoritmo evolutivo basado en poblaciones que evoluciona soluciones en subgrafos.
• Introducción de un operador de cruce alélico generalizado que generaliza el cruce uniforme.
• Análisis del tiempo de ejecución esperado para la cobertura de k-vértices utilizando mutaciones estilo RLS y restringidas.

Principales resultados:

• El algoritmo resuelve el problema de la cobertura de k-vértices en tiempo esperado O(4km+m4logn) con mutación estilo RLS.
• El tiempo de ejecución mejora a O(4km+m2nklogn) con mutación restringida.
• Un algoritmo modificado encuentra subgrafos k-cubiertos máximos con alta probabilidad dentro de un tiempo de ejecución de Ω(2km3log2n).
• Los resultados empíricos muestran que los subgrafos generados retienen las propiedades estructurales del grafo fuente.

Conclusiones:

• El enfoque propuesto basado en poblaciones ofrece un método eficiente para problemas de grafos parametrizados.
• El operador de cruce alélico generalizado combina eficazmente soluciones de subgrafos.
• La capacidad de generar subgrafos estructuralmente representativos tiene implicaciones para la evaluación comparativa de grafos.