# SuperNOVA: a novel algorithm for graph automorphism calculations

Source: [SuperNOVA: a novel algorithm for graph automorphism calculations](<https://www.sota2.com/research/paper/68fa61b91e209131ce9f5c32>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:30.229Z

Authors: Russell K. Standish

Published: 2009-05-24T22:44:38.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/0905.3927>)

[PDF](<https://arxiv.org/pdf/0905.3927.pdf>)
