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 the, state of, state and/or art:
“The concept of a mental state is primarily the concept of a state of the person apt for bringing about a certain sort of behaviour.”
—David Malet Armstrong (b. 1926)
“The educated do not share a common body of information, but a common state of mind.”
—Mason Cooley (b. 1927)
“Realizing that his time was nearly spent, he gave full oral instructions about his burial and the manner in which he wished to be remembered.... A few minutes later, feeling very tired, he left the room, remarking, ‘I have no disposition to leave this precious circle. I love to be here surrounded by my family and friends.’ Then he gave them his blessing and said, ‘I am ready to go and I wish you goodnight.’”
—For the State of New Hampshire, U.S. public relief program (1935-1943)
“Fear no more the frown o’ th’ great,
Thou art past the tyrant’s stroke;
Care no more to clothe and eat,
To thee the reed is as the oak.
The sceptre, learning, physic, must
All follow this and come to dust.”
—William Shakespeare (1564–1616)