Path: utzoo!attcan!uunet!crdgw1!rpi!uupsi!sunic!dkuug!imada!paw
From: paw@imada.dk (Paw Hermansen)
Newsgroups: comp.theory
Subject: Graph isomorphism, summary
Summary: summary
Keywords: graph, isomorhism, algorithm, complexity
Message-ID: <787@imada.dk>
Date: 30 Jul 90 14:42:46 GMT
Distribution: comp
Organization: Dept. of Math. & Computer Science, Odense University, Denmark
Lines: 27


   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)