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 the art, state of, state and/or art:
“The past is interesting not only for the beauty which the artists for whom it was the present were able to extract from it, but also as past, for its historical value. The same goes for the present. The pleasure which we derive from the representation of the present is due not only to the beauty in which it may be clothed, but also from its essential quality of being present.”
—Charles Baudelaire (1821–1867)
“I can never suppose this country so far lost to all ideas of self-importance as to be willing to grant America independence; if that could ever be adopted I shall despair of this country being ever preserved from a state of inferiority and consequently falling into a very low class among the European States.”
—George III (1738–1820)
“Such is my jealousy and such my hate
though I would state it otherwise.”
—Hilda Doolittle (1886–1961)
“Life is short, the art long, opportunity fleeting, experiment treacherous, judgment difficult.”
—Hippocrates (c. 460–370 B.C.)