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:
“In the Corner Store, near the village center, hangs a large sign reading: ‘After 40 years of credit business, we have closed our book of Sorrow.’”
—For the State of Maine, U.S. public relief program (1935-1943)
“There is nothing worse than an idle hour, with no occupation offering. People who have many such hours are simply animals waiting docilely for death. We all come to that state soon or late. It is the curse of senility.”
—H.L. (Henry Lewis)
“Abused as we abuse it at present, dramatic art is in no sense cathartic; it is merely a form of emotional masturbation.... It is the rarest thing to find a player who has not had his character affected for the worse by the practice of his profession. Nobody can make a habit of self-exhibition, nobody can exploit his personality for the sake of exercising a kind of hypnotic power over others, and remain untouched by the process.”
—Aldous Huxley (1894–1963)