Novel Techniques for Automorphism Group Computation
| Autor: | José Luis López-Presa, Luis Núñez Chiroque, Antonio Fernández Anta |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Informática
SPQR tree Matemáticas Voltage graph 0102 computer and information sciences 02 engineering and technology Tree-depth 01 natural sciences Search tree Edge-transitive graph 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing Graph automorphism Algorithm Mathematics Moral graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IMDEA Networks Institute Digital Repository IMDEA Networks Institute Experimental Algorithms: 12th International Symposium, SEA 2013, Rome, Italy Italy, June 5-7, 2013, Proceedings | 12th International Symposium on Experimental Algorithms, Rome, Italy, June 5-7, 2013 (SEA 2013) | 05/06/2013-07/06/2013 | Roma, Italia Archivo Digital UPM Universidad Politécnica de Madrid Experimental Algorithms ISBN: 9783642385261 SEA instname |
| Popis: | Springer 2013 Lecture Notes in Computer Science ISBN 978-3-642-38526-1 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. TRUE pub |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|