View source for Talk:Tarjan's off-line lowest common ancestors algorithm

{{WikiProject banner shell|class=Start|
{{WikiProject Mathematics|priority=Low}}
}}

==Analysis==
It would be great if someone added a paragraph about the analysis, or at least about the complexity... [[Special:Contributions/85.218.28.6|85.218.28.6]] ([[User talk:85.218.28.6|talk]]) 21:04, 11 October 2009 (UTC)

==Copyright==
I think that this article needs to be examined for possible copyright issues.  The pseudocode is taken directly from "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ''Introduction to Algorithms'', MIT Press and McGraw-Hill, 1990."  (I looked at this earlier today when the database was locked — I can provide a page reference the next time I look at the book.) [[User:Boris Alexeev|Boris Alexeev]] 19:26, 11 September 2005 (UTC)
: Page 521 perhaps.

==Inventors==
The algorithm itself is not invented by Tarjan, but rather by Aho, Hopcroft and Ullman (see Tarjan - Efficiency of a Good But Not Linear Set Union Algorithm, JACM Volume 22 ,  Issue 2  (April 1975), Pages: 215 - 225). So this must be a mistake in Cormen at al. I believe this article must be renamed or removed. -- Andrew Stankevich
:Lots of mathematical results are named after the wrong person. That doesn't make the results incorrect, and doesn't even mean they should be renamed. We are not here to correct the scientific nomenclature but to report on it. But, the earlier invention should be described in the article. —[[User:David Eppstein|David Eppstein]] 14:40, 30 July 2007 (UTC)

==Least==
Why is it called '''least''' common ancestor? I mean "least common" suggests "non common", and so the root (being an ancestor of every node) would be the answer to all queries.  [[User:Devika.shaumslager|Devika.shaumslager]] ([[User talk:Devika.shaumslager|talk]]) 07:27, 21 August 2008 (UTC)
:The terminology is related to tree partial orders. If you are given a rooted tree T with root r it induces a partial order on its vertices where u <= v iff v lies on the unique path from r to u. In this order the "least upper bound" of two elements corresponds to their "least common ancestor".  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/80.133.218.54|80.133.218.54]] ([[User talk:80.133.218.54|talk]]) 16:20, 5 February 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

==Animation==
Request for an animation illustrating the algorithm (i.e., showing the state transitions and how the algorithm produces them).  (Yes, I know that Wikipedia is a DIY site, but I have nowhere near the level of expertise necessary to fulfill my own request in less than exponential time.)   Thanks![[User:OlyDLG|OlyDLG]] ([[User talk:OlyDLG|talk]]) 01:47, 22 November 2015 (UTC)