Novel techniques for automorphism group computation

López Presa, Jose Luis; Núñez Chiroque, Luis y Fernández Anta, Antonio (2013). Novel techniques for automorphism group computation. En: "12th International Symposium on Experimental Algorithms, Rome, Italy, June 5-7, 2013 (SEA 2013)", 05/06/2013 - 07/06/2013, Roma, Italia. ISBN 9783642385278. pp. 296-307. https://doi.org/10.1007/978-3-642-38527-8_27.

Descripción

Título: Novel techniques for automorphism group computation
Autor/es:
  • López Presa, Jose Luis
  • Núñez Chiroque, Luis
  • Fernández Anta, Antonio
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 12th International Symposium on Experimental Algorithms, Rome, Italy, June 5-7, 2013 (SEA 2013)
Fechas del Evento: 05/06/2013 - 07/06/2013
Lugar del Evento: Roma, Italia
Título del Libro: Experimental Algorithms: 12th International Symposium, SEA 2013, Rome, Italy Italy, June 5-7, 2013, Proceedings
Fecha: 2013
ISBN: 9783642385278
Volumen: 7933
Materias:
Escuela: E.U.I.T. Telecomunicación (UPM) [antigua denominación]
Departamento: Ingeniería y Arquitecturas Telemáticas [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (420kB) | Vista Previa

Resumen

Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. In this work we propose four novel techniques to speed up algorithms that solve the GA problem by exploring a search tree. They increase the performance of the algorithm by allowing to reduce the depth of the search tree, and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of the input graph. We also describe how the techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity. We have experimentally evaluated the impact of each of the above techniques with several graph families. We have observed that each of the techniques by itself significantly reduces the number of processed nodes of the search tree in some subset of graphs, which justifies the use of each of them. Then, when they are applied together, their effect is combined, leading to reductions in the number of processed nodes in most graphs. This is also reflected in a reduction of the running time, which is substantial in some graph families.

Proyectos asociados

TipoCódigoAcrónimoResponsableTítulo
Comunidad de MadridS2009TIC-1692Sin especificarSin especificarSin especificar

Más información

ID de Registro: 33299
Identificador DC: http://oa.upm.es/33299/
Identificador OAI: oai:oa.upm.es:33299
Identificador DOI: 10.1007/978-3-642-38527-8_27
URL Oficial: http://sea2013.dis.uniroma1.it/
Depositado por: Memoria Investigacion
Depositado el: 17 Abr 2015 18:06
Ultima Modificación: 25 May 2015 14:02
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM