Use of Automorphisms in Conauto-2.0

Núñez Chiroque, Luis Felipe (2011). Use of Automorphisms in Conauto-2.0. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.U.I.T. Telecomunicación (UPM).

Description

Title: Use of Automorphisms in Conauto-2.0
Author/s:
  • Núñez Chiroque, Luis Felipe
Contributor/s:
  • López Presa, José Luis
Item Type: Final Project
Date: 28 October 2011
Subjects:
Faculty: E.U.I.T. Telecomunicación (UPM)
Department: Ingeniería y Arquitecturas Telemáticas [hasta 2014]
Creative Commons Licenses: Recognition

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

Se ha realizado un estudio de los fundamentos matemáticos de la teoría de grafos, la cual tiene varios problemas abiertos. Uno de estos problemas es el del isomorfismo de un subgrafo, del cual podemos sacar un caso particular de él, que es el problema del isomorfismo de grafos. El problema del isomorfismo de grafos tiene interés, tanto desde el punto de vista teórico, como práctico. Desde el punto de vista teórico es interesante porque existen variedad de problemas que son reducibles al del isomorfismo de grafos. Por lo tanto, encontrar un algoritmo que resuelva este problema en tiempo polinómico, resolvería indirectamente estos otro problemas también en tiempo polinómico. Desde el punto de vista práctico, resulta útil en muchos campos, desde el reconocimiento de formas a la química matemática, donde es imprescindible para catalogar adecuadamente los compuestos químicos. Partiendo del algoritmo conauto-1.02, se han añadido nuevas funcionalidad, conservando el enfoque original, para mejorar su rendimiento. Los más actuales y rápidos algoritmos para resolver el problema del isomorfismo de grafos están basados en etiquetado canónico. Sin embargo, normalmente es mucho más difícil encontrar un etiquetado canónico para un grafo, que calcular su grupo de automorfismo. Por lo tanto, un algoritmo que calcule el grupo de automorfismo de los grafos a comprobar dicho isomorfismo, e intente casarlos usando esta información, podría dar lugar a un algoritmo que sea más rápido que aquellos basados en etiquetado canónico. Con todo esto, hemos desarrollado un algoritmo, conauto-2.0, que usa este enfoque alternativo. Una característica en común de todos estos algoritmo (incluido conauto) es que están basados en la técnica de individualización-refinamiento. Los puntos clave en la individualización son los criterios para seleccionar la celda de la cual se individualizará un vértice. En conauto-2.0 la selección de la celda para individualizar es parcialmente dinámica, e intenta reducir el número de puntos de 'backtrack' tanto como le sea posible. Esto es una contribución parcial de este trabajo, pero que ayuda a mejorar el rendimiento. Las más importantes contribuciones de este trabajo son los teoeremas basados en el concepto de sub-partición. El primer teorema permite la detección prematura de automorfismos sin la necesidad de generar la correspondiente secuencia de particiones completa, lo cual acelera el algoritmo en muchos casos. El segundo teorema ayuda a podar secciones completas del árbol de búsqueda para los casos de búsqueda de automorfismos y la búsqueda de secuencia de particiones compatibles, usando 'backjumping'. Estas características de conauto-2.0 lo hacen superar al resto de algoritmos con las familias de grafos basados en componentes, y además su campo de aplicación no está solamente limitado a estas familias de grafos. Se realizaron pruebas de isomorfismo de grafos y de cálculo de grupo de automorfismo para nuestro algoritmo, contra algunos de los actuales y más conocidos algoritmos de resolución de dichos problemas. Los resultados mostraron que conauto-2.0 tiene el comportamiento más regular, además de ser el algoritmo más rápido para varias familias de grafos.

More information

Item ID: 10045
DC Identifier: http://oa.upm.es/10045/
OAI Identifier: oai:oa.upm.es:10045
Deposited by: Sr. Luis Felipe Núñez Chiroque
Deposited on: 15 Jan 2012 16:21
Last Modified: 20 Apr 2016 18:19
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM