Re: query that Bob is descendant of Alice

Mats Kindahl <matkin_at_iar.se> wrote:
>The call tree you have form a DAG, but I believe the following can be
>easily applied to DAGs and to "forests" as well [...]

And there is the trick. In DAGs, you have multiple LCAs. Besides getting uncertain, algorithm would IMHO need modifications for DAGs, so I would need look in detail on that algo.

<snipped adaptation of LCA to is_descendant question>

>[2] D. Harel and R. E. Tarjan.
> Fast algorithms for finding nearest common ancestors.
> SIAM J. Comput., 13:338-355, 1984.
>
>[3] B. Schieber and U. Vishkin.
> On finding lowest common ancestors: simplification and
> parallelization. SIAM J. Comput., 17(6):1253-1262,
> December 1988.

It is sad, but for me, if it is not online, it doesn't exist. Is there a web site with LCA or author's homepage? Could you describe key steps of LCA? It's hard to guess.

/Robert Received on Mon Apr 23 2001 - 17:56:45 CDT