Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation

Details Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation

2011-08-04

arxiv.org/abs/1108.1060v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we present an algorithm, called conauto-2.0, that can efficiently compute a set of generators of the automorphism group of a graph, and test whether two graphs are isomorphic, finding an isomorphism if they are. This algorithm uses the basic individualization/refinement technique, and is an improved version of the algorithm conauto, which has been shown to be very fast for random graphs and several families of hard graphs. In this paper, it is proved that, under some circumstances, it is not only possible to prune the search space (using already found generators of the automorphism group), but also to infer new generators without the need of explicitly finding an automorphism of the graph. This result is especially suited for graphs with regularly connected components, and can be applied in any isomorphism testing and canonical labeling algorithm (that use the individualization/refinement technique) to significantly improve its performance. Additionally, a dynamic target cell selection function is used to adapt to different graphs. The resulting algorithm preserves all the nice features of conauto, but reduces the time for testing graphs with regularly connected components and other hard graph families. We run extensive experiments, which show that the most popular algorithms (namely, nauty, bliss, Traces, and saucy) are slower than conauto-2.0, among others, for the graph families based on components.

Affiliated with

Also associated with

No associations

Rating

Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14254