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
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
0.953304886817932
0 references
0.9216784238815308
0 references
0.9020679593086244
0 references
0.892339289188385
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