Resumen

El automorfismo de grafos (GA) es un problema clásico, cuyo objetivo es calcular el grupo de automorfismos de un grafo de entrada. La mayoría de los algoritmos de GA exploran un árbol de búsqueda utilizando el procedimiento de individualización-refinamiento. Se proponen cuatro técnicas novedosas que aumentan el rendimiento de cualquier algoritmo de este tipo al reducir la profundidad del árbol de búsqueda y podarlo de manera efectiva. Demostramos formalmente que un algoritmo de GA que utiliza estas técnicas calcula correctamente el grupo de automorfismos de un grafo de entrada. Luego, describimos cómo estas técnicas se han incorporado al algoritmo de GA conauto, con un aumento polinomial aditivo en su complejidad temporal asintótica. Utilizando un conjunto de pruebas de diferentes familias de grafos, hemos evaluado el impacto de estas técnicas en el tamaño del árbol de búsqueda, observando una reducción significativa tanto cuando se aplican individualmente como cuando se aplican todas juntas. Esto también se refleja en una reducción del tiempo de

• Materias:Modelos matemáticos Conjuntos difusos Ecuaciones integrales Fusión de características Algoritmo de optimización
• Subjects:Mathematical models Fuzzy sets Integral equations Feature fusion Optimization algorithm
• Palabras claves:Isomorfismo de grafo; Algoritmos; árbol de búsqueda; Técnicas; Grupo de automorfismo; Rendimiento
• Keywords:Graph automorphism; Algorithms; Search tree; Techniques; Automorphism group; Performance