84:
74:
53:
22:
204:
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
244:
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".
209:
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.
272:
Request for an animation illustrating the algorithm (i.e., showing the state transitions and how the algorithm produces them). (Yes, I know that
Knowledge is a DIY site, but I have nowhere near the level of expertise necessary to fulfill my own request in less than exponential time.)
181:
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,
140:
185:, 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.)
301:
130:
296:
229:
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.
106:
252:
163:
97:
58:
282:
260:
238:
214:
189:
171:
33:
234:
21:
256:
230:
167:
39:
162:
It would be great if someone added a paragraph about the analysis, or at least about the complexity...
83:
248:
211:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
274:
186:
89:
73:
52:
278:
290:
102:
79:
15:
101:, a collaborative effort to improve the coverage of
8:
19:
47:
49:
7:
95:This article is within the scope of
38:It is of interest to the following
14:
302:Low-priority mathematics articles
205:or removed. -- Andrew Stankevich
115:Knowledge:WikiProject Mathematics
297:Start-Class mathematics articles
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
190:19:26, 11 September 2005 (UTC)
1:
283:01:47, 22 November 2015 (UTC)
109:and see a list of open tasks.
261:16:20, 5 February 2012 (UTC)
172:21:04, 11 October 2009 (UTC)
239:07:27, 21 August 2008 (UTC)
318:
183:Introduction to Algorithms
215:14:40, 30 July 2007 (UTC)
134:
67:
46:
141:project's priority scale
98:WikiProject Mathematics
28:This article is rated
121:mathematics articles
231:Devika.shaumslager
90:Mathematics portal
34:content assessment
251:comment added by
225:Why is it called
195:Page 521 perhaps.
155:
154:
151:
150:
147:
146:
309:
263:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
317:
316:
312:
311:
310:
308:
307:
306:
287:
286:
270:
246:
223:
202:
179:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
315:
313:
305:
304:
299:
289:
288:
269:
266:
265:
264:
222:
219:
218:
217:
212:David Eppstein
201:
198:
197:
196:
178:
175:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
314:
303:
300:
298:
295:
294:
292:
285:
284:
280:
276:
267:
262:
258:
254:
253:80.133.218.54
250:
243:
242:
241:
240:
236:
232:
228:
220:
216:
213:
208:
207:
206:
199:
194:
193:
192:
191:
188:
187:Boris Alexeev
184:
176:
174:
173:
169:
165:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
271:
247:— Preceding
226:
224:
203:
182:
180:
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
164:85.218.28.6
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
291:Categories
268:Animation
200:Inventors
177:Copyright
249:unsigned
158:Analysis
273:Thanks!
139:on the
275:OlyDLG
36:scale.
227:least
221:Least
279:talk
257:talk
235:talk
168:talk
131:Low
293::
281:)
259:)
237:)
170:)
277:(
255:(
233:(
210:—
166:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
