SuperNOVA: a novel algorithm for graph automorphism calculations

Details SuperNOVA: a novel algorithm for graph automorphism calculations SuperNOVA: a novel algorithm for graph automorphism calculations

2009-05-24

arxiv.org/abs/0905.3927v1

Computer Science

Data Structures and Algorithms

Scientific paper

The graph isomorphism problem is of practical importance, as well as being a theoretical curiosity in computational complexity theory in that it is not known whether it is $NP$-complete or $P$. However, for many graphs, the problem is tractable, and related to the problem of finding the automorphism group of the graph. Perhaps the most well known state-of-the art implementation for finding the automorphism group is Nauty. However, Nauty is particularly susceptible to poor performance on star configurations, where the spokes of the star are isomorphic with each other. In this work, I present an algorithm that explodes these star configurations, reducing the problem to a sequence of simpler automorphism group calculations.

Affiliated with

Also associated with

No associations

Rating

SuperNOVA: a novel algorithm for graph automorphism calculations 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 SuperNOVA: a novel algorithm for graph automorphism calculations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and SuperNOVA: a novel algorithm for graph automorphism calculations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293750