fix for a keyerror in finding least common ancestors

[Robert Collins]

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

-Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070731/7daf0edb/attachment.pgp