No label defined (Q3798229)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4064469
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4064469

      Statements

      0 references
      0 references
      1988
      0 references
      rooted tree
      0 references
      lowest common ancestor
      0 references
      parallel preprocessing algorithm
      0 references
      logarithmic time
      0 references
      EREW PRAM
      0 references
      [For the entire collection see Zbl 0643.00025.] We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm which enables us to answer each query in O(1) time, as in \textit{D. Harel} and \textit{R. E. Tarjan} [SIAM J. Comput. 13, 338-355 (1984; Zbl 0535.68022)]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in O(1) time using a single processor.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references