Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Tarjan's off-line lowest common ancestors algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, Tarjan's off-line lowest common ancestors algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for computing <a href="/facts/Lowest_common_ancestor/lUuLKAGk">lowest common ancestors</a> for pairs of nodes in a tree, based on the <a href="/facts/Union-find/QnFQNedE">union-find</a> data structure. The lowest common ancestor of two nodes <i>d</i> and <i>e</i> in a <a href="/facts/Rooted_tree/TCWk4Joy">rooted tree</a> <i>T</i> is the node <i>g</i> that is an ancestor of both <i>d</i> and <i>e</i> and that has the greatest depth in <i>T</i>. It is named after <a href="/facts/Robert_Tarjan/kn1pMCN0">Robert Tarjan</a>, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by Gabow & Tarjan (1983) speeds the algorithm up to <a href="/facts/Linear_time/77T62gmf">linear time</a>. </p>