Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: query that Bob is descendant of Alice

Re: query that Bob is descendant of Alice

From: Robert Vazan <robova_at_nextra.sk>
Date: Mon, 23 Apr 2001 22:56:45 GMT
Message-ID: <3ae49188.2013958@news.nextra.sk>

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

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US