Skip to main content
7 of 12
add some information

What's the worst case for strongly regular graph's isomorphism algorithm?

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{log n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!