Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem)

Time Complexity

\exp(n^{\frac{1}{2} + $O({1})$})

Space Complexity

$O(n^{2})$ words

(https://epubs.siam.org/doi/epdf/10.1137/0209018)

Approximate?

Exact

Randomized?

Yes, Las Vegas

Model of Computation

Word RAM

Year

1980

Reference

https://epubs.siam.org/doi/10.1137/0209018