3 ms·

This makes me nervous: Further, without loss of generality of the task, we will consider undirected connected graphs without loops. Tree isomorphism is polyno

by jfoutz 17y ago

This makes me nervous: Further, without loss of generality of the task, we will consider undirected connected graphs without loops. Tree isomorphism is polynomial. It's not obvious to me how you cut the loops out of two graphs and ensure you end up with similar trees. Quick scan didn't show that in the paper. I guess i'll have to read in more detail after dinner.

leif 17y ago
Loops as in "edges from vertex a to vertex a", not cycles, were discounted. That's fine because you can ignore them until the end, and then just check your vertices for any loops, in O(n) time.
- jfoutz 17y ago
  ah! that makes a whole lot more sense. thanks.