[comp.theory] Graph isomorphism, summary

paw@imada.dk (Paw Hermansen) (07/30/90)

   About a week ago I asked for information about GRAPH
ISOMORPHISM. Here is a short summary of the answers:

1. The theoretical fastest algorithm, that works on
   *all* graphs, has a time complexity of about
   exp( O(sqrt(n)) ), and it probably has no practical
   use.

2. It is still not known if the problem can be solved
   in polynomial time or not.


  I found what I wanted from the references in the book
"Random Graphs" by Bollobas, Academic Press 1985.


3. There exists very fast algorithms that works for
   most graphs but not for all. Bollobas mention one
   that works in O(n^2) worst case time for most graphs
   and in O(n^2) expected time for all graphs.


Thanks to those who answered me.

paw@imada.dk
(Paw Hermansen)