Novel techniques for automorphism group computation

López Presa, Jose Luis and Núñez Chiroque, Luis and Fernández Anta, Antonio (2013). Novel techniques for automorphism group computation. In: "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.

Description

Title: Novel techniques for automorphism group computation
Author/s:
  • López Presa, Jose Luis
  • Núñez Chiroque, Luis
  • Fernández Anta, Antonio
Item Type: Presentation at Congress or Conference (Article)
Event Title: 12th International Symposium on Experimental Algorithms, Rome, Italy, June 5-7, 2013 (SEA 2013)
Event Dates: 05/06/2013 - 07/06/2013
Event Location: Roma, Italia
Title of Book: Experimental Algorithms: 12th International Symposium, SEA 2013, Rome, Italy Italy, June 5-7, 2013, Proceedings
Date: 2013
ISBN: 9783642385278
Volume: 7933
Subjects:
Faculty: E.U.I.T. Telecomunicación (UPM)
Department: Ingeniería y Arquitecturas Telemáticas [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

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

Abstract

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.

Funding Projects

TypeCodeAcronymLeaderTitle
Madrid Regional GovernmentS2009TIC-1692UnspecifiedUnspecifiedUnspecified

More information

Item ID: 33299
DC Identifier: http://oa.upm.es/33299/
OAI Identifier: oai:oa.upm.es:33299
DOI: 10.1007/978-3-642-38527-8_27
Official URL: http://sea2013.dis.uniroma1.it/
Deposited by: Memoria Investigacion
Deposited on: 17 Apr 2015 18:06
Last Modified: 25 May 2015 14:02
  • 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