Re: Distance among trees

[cacharbe]

A quick google search gave me these (this and this which look promising) and also lead me to this, which should also prove useful.

C-.

Update:My final suggestion, as I mentioned below, would be to talk to some of the people at Journal of Graph Algorithms and Applications. Someone like Mihalis Yannakakis, I mean, check out the first publication on his bibliography.

[jmerelo]

Already followed those leads, even emailed the guy. Looks promising, but uses its own version of trees, creates "bipartition" of them, and does not contain a detailed explanation of the algorithm. I could try and glean it by following the code, but I'm not sure it's worth the while.

[cacharbe]

Looks like you're going to have to find a copy of "Lecture notes in mathematics" --Springer-Verlag, Germany(1979) to find out their proposed algorithm (or one of Foulds' other books, and he seems to have a few), but I found a text description of it here, pg. 4, and a subsequent discussion on the "Deltahedron Method" here, which does give an algorithm, but doesn't necessarily describe it as Foulds'.

Hope that helps,

C-.

Update: After reading the Caccetta/Kusumah text, theirs might be a more interesting algorithm to attempt implementing if you are going to start from scratch.

[jmerelo]

Not exactly what I was looking for. That's _another_ Robinson-Foulds algorithm, not for tree distances. I am not sure I want RF algorithm; looks like it's used for taxonomic distances, but I'm looking for something similar to the insertion-and-deletion metric for strings, but applied to trees. Does that exist?

[jmerelo]

Not exactly what I was looking for; looks like a tree construction method.