Novel techniques to speed up the computation of the automorphism group of a graph
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Analysis of algorithms and problem complexity (68Q25)
Summary: Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. Most GA algorithms explore a search tree using the individualization-refinement procedure. Four novel techniques are proposed which increase the performance of any algorithm of this type by reducing 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 an input graph. Then, we describe how these techniques have been incorporated into the GA algorithm conauto, as \textit{conauto-2.03}, with at most an additive polynomial increase in its asymptotic time complexity. Using a benchmark of different graph families, we have evaluated the impact of these techniques on the size of the search tree, observing a significant reduction both when they are applied individually and when all of them are applied together. This is also reflected in a reduction of the running time, which is substantial for some graph families. Finally, we have compared the search tree size of conauto-2.03 against those of other popular GA algorithms, observing that, in most cases, conauto explores less nodes than these algorithms.
- A large database of graphs and its use for benchmarking graph isomorphism algorithms
- Attacks on hard instances of graph isomorphism
- Conflict Anticipation in the Search for Graph Automorphisms
- Conflict propagation and component recursion for canonical labeling
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Experimental algorithms. 8th international symposium, SEA 2009, Dortmund, Germany, June 4--6, 2009. Proceedings
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 1004939 (Why is no real title available?)
- Improved random graph isomorphism
- On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
- Practical graph isomorphism. II.
- PSL(2,q) as a collineation group of projective planes of small order
- Symmetry and Satisfiability: An Update
- Classical symmetries and the quantum approximate optimization algorithm
- Conflict propagation and component recursion for canonical labeling
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Search problems in trees with symmetries: near optimal traversal strategies for individualization-refinement algorithms
This page was built for publication: Novel techniques to speed up the computation of the automorphism group of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2336847)
