[Corpora-List] Algorithm for hypernym chaining?

[Adam Funk]

Sorry if this is a bit off-topic, but at least it's for an NLP
application.  I have a file of pairs of WordNet synset numbers that
represent hypernym-hyponym pairs, for example:

100001930,100001740
100002137,100001740
100002452,100001930
100002684,100001930
100003553,100002684
100003993,100003553
100004258,100003553
100004475,100004258
100005787,100004475
100005930,100004475

and I want to produce all the longest possible chains of them.  The
output for that list is as follows:

100002137,100001740
100002452,100001930,100001740
100003993,100003553,100002684,100001930,100001740
100005787,100004475,100004258,100003553,100002684,100001930,100001740
100005930,100004475,100004258,100003553,100002684,100001930,100001740

I have a program that does this correctly for small samples of the data
I'm supposed to process, but I've estimated (using a log plot) that it
will take about 10^595 seconds to run over the whole list (about 89000
pairs), so I think I'm doing it wrong.

I haven't been able to find an algorithm for this, because I don't know
what the computational problem is called.  Can anyone point me in the
direction of something suitable?

_______________________________________________
Corpora mailing list
Corpora at uib.no
http://mailman.uib.no/listinfo/corpora