home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1746 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.6 KB
  1. Path: sparky!uunet!olivea!decwrl!mips!darwin.sura.net!jvnc.net!phage!wchang
  2. From: wchang@cshl.org (Bill Chang)
  3. Newsgroups: comp.theory
  4. Subject: Re: Algorithm for lowest common ancestor problem
  5. Message-ID: <1992Aug12.170222.3859@cshl.org>
  6. Date: 12 Aug 92 17:02:22 GMT
  7. References: <ARUN.92Aug11192510@bayou22.cacs.usl.edu>
  8. Sender: news@cshl.org (NO MAIL)
  9. Organization: Cold Spring Harbor Laboratory
  10. Lines: 25
  11.  
  12. B. Schieber and U. Vishkin, On Finding Lowest Common Ancestors: Simplification
  13.     and Parallelization, {\em SIAM J. Comput.} 17:6(1988), pp. 1253--1262.
  14.  
  15. Linear space and preprocessing of the tree; constant time LCA queries using
  16. bit magic.  I have implemented this algorithm (for string matching; my tree
  17. is a digital trie).  Runs in about 50 simple machine instructions per query.
  18.  
  19. There is a newer alogorithm
  20.  
  21. O. Berkman and U. Vishkin, Recursive *-tree Parallel Data-Structure (1989)
  22.  
  23. which is discussed in Joseph Ja Ja's terrific new book An Intro. to Parallel
  24. Algorithms (Addison-Wesley 1992).
  25.  
  26. These methods are based on deep analyses of node numbering given by tree 
  27. traversals.  If your tree is not too large, a quadratic space tabulation
  28. (computed "top-down" so to speak) of all LCA(x,y) may suffice.  The simplest
  29. method is probably to store with each node its distance from the root...
  30. Next simplest is to number the nodes so a subtree corresponds to an interval
  31. of numbers...  If the tree cannot be preprocessed, compute the paths to the
  32. root, then compare them starting from the root.  
  33.  
  34. In practice simpler methods may very well be faster :-)
  35.  
  36. -- Bill Chang (wchang@cshl.org)                Cold Spring Harbor Lab., NY
  37.