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:
“In every particular state of the world, those nations which are strongest tend to prevail over the others; and in certain marked peculiarities the strongest tend to be the best.”
—Walter Bagehot (1826–1877)
“Resorts advertised for waitresses, specifying that they “must appear in short clothes or no engagement.” Below a Gospel Guide column headed, “Where our Local Divines Will Hang Out Tomorrow,” was an account of spirited gun play at the Bon Ton. In Jeff Winney’s California Concert Hall, patrons “bucked the tiger” under the watchful eye of Kitty Crawhurst, popular “lady” gambler.”
—Administration in the State of Colo, U.S. public relief program (1935-1943)
“Being the dependents of the general government, and looking to its treasury as the source of all their emoluments, the state officers, under whatever names they might pass and by whatever forms their duties might be prescribed, would in effect be the mere stipendiaries and instruments of the central power.”
—Andrew Jackson (1767–1845)
“Blind mouths! that scarce themselves know how to hold
A sheephook, or have learn’d ought else the least
That to the faithful herdman’s art belongs!
What recks it them? What need they? They are sped.
And when they list their lean and flashy songs
Grate on their scrannel pipes of wretched straw,
The hungry sheep look up, and are not fed,”
—John Milton (1608–1674)