lowest superordinate of two concepts in a taxonomy

How to find the lowest superordinate of two concepts in an efficient way? The lowest superordinate of two concepts in a taxonomy means the most specific common ancestor of the t开发者_JS百科wo concepts. For example, in the following picture of a taxonomy, how find the most common ancestor of sense 1 and sense 2?

BTW, I found this question in Roberto Navigli's survey of word sense disambiguation. He didn't mention how to compute the superordinate.

---

You could go up the hierarchy from the Sense 1 side and mark all of those nodes as ancestors of Sense 1. Then go up the Sense 2 side and check each ancestor to see if you marked it as an ancestor of Sense 1. The first one you find would be the lowest superordinate or most specific common ancestor.

In your picture, it would be the root node no matter which senses you start from.

---

http://en.wikipedia.org/wiki/Lowest_common_ancestor contains pointers to more efficient algorithms for the least common ancestor problem in the (usual) case where we have a tree, so every node has one parent, except for the root node, which has no parent. These algorithms can answer queries in constant time, after linear time pre-processing of the tree.

I do not know if any of these algorithms would generalise to the case where you can have more than one parent. It looks like the obvious generalisations would amount to deleting links in your tree to make sure that, while still connected, every node had at most one parent.