fix for a keyerror in finding least common ancestors

[Michael Hudson]

Robert Collins wrote:
> On Mon, 2007-07-30 at 15:47 +0100, Michael Hudson wrote:
> 
> 
>>> I'm not really familiar with graph theory terminology.  I'd appreciate
>>> any suggestions you can offer, and I'm also happy to explain everything
>>> in the file already.
>> I don't either.  I just glanced at a few papers after googling some
>> likely terms, but the papers I found were all solving the problem in a
>> rather different way (we show how to answer the LCA problem in constant
>> time given O(n**2.7) steps of preprocessing...)
> 
> Most references to the "LCA" problem aim to solve it for all possible
> pairs of keys; it may be worth implementing an updatable
> preprocessed-answer finder at some point,

Not if the exponents are this large, though.  Even if you can make it
incremental, O(n**1.7) work on each commit might not be popular :-)

> but as our common case is keys
> in a small region (< 1% of the graph space) apart, local walking is
> really much easier.

Do you know of any research on this problem?

Cheers,
mwh