State of The Art
The best current theoretical algorithm is due to Eugene Luks (1983), and is based on the earlier work by Luks (1981), Babai & Luks (1982), combined with a subfactorial algorithm due to Zemlyachenko (1982). The algorithm relies on the classification of finite simple groups. Without CFSG, a slightly weaker bound 2O(√n log2 n) was obtained first for strongly regular graphs by László Babai (1980), and then extended to general graphs by Babai & Luks (1982). Improvement of the exponent √n is a major open problem; for strongly regular graphs this was done by Spielman (1996). For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs, was recently obtained by Babai & Codenotti (2008).
On a side note, the graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem, and the permutation group intersection problem. For the latter two problems, Babai, Kantor and Luks (1983) obtained complexity bounds similar to that for the graph isomorphism.
There are several competing practical algorithms for graph isomorphism, due to McKay (1981), Schmidt & Druffel (1976), Ullman (1976), etc. While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case.
Read more about this topic: Graph Isomorphism Problem
Famous quotes containing the words state of, state and/or art:
“When I saw it I was so glad I could not speak. My eyes seemed too little to see it all.... I was a long time without speaking to my friend. To see me always looking and never speaking he thought I had lost my mind. I could not understand where all this could come from.”
—For the State of Maine, U.S. public relief program (1935-1943)
“The essence of the modern state is that the universal be bound up with the complete freedom of its particular members and with private well-being, that thus the interests of family and civil society must concentrate themselves on the state.... It is only when both these moments subsist in their strength that the state can be regarded as articulated and genuinely organized.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“Truly, My Satan, thou art but a Dunce,
And dost not know the Garment from the Man.
Every Harlot was a Virgin once,
Nor can’st thou ever change Kate into Nan.”
—William Blake (1757–1827)