ON FINDING LOWEST COMMON ANCESTORS - SIMPLIFICATION AND PARALLELIZATION

被引：317

作者：

SCHIEBER, B

VISHKIN, U

机构：

[1] TEL AVIV UNIV,SCH MATH SCI,DEPT COMP SCI,IL-69978 TEL AVIV,ISRAEL

[2] NYU,COURANT INST MATH SCI,DEPT COMP SCI,NEW YORK,NY 10012

来源：

SIAM JOURNAL ON COMPUTING | 1988年 / 17卷 / 06期

关键词：

Computer Systems; Digital--Parallel Processing - Mathematical Techniques--Trees;

D O I：

10.1137/0217079

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 that enables us to answer each query in O(1) time. 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.

引用

页码：1253 / 1262

页数：10

共 12 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

APOSTOLICO A, IN PRESS ALGORITHMIC

[3]

Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P478, DOI 10.1109/SFCS.1986.10

[4]

COLE R, 1986, TR5686 TEL AV U I CO

[5] FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS [J].

HAREL, D ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :338-355

[6]

LANDAU GM, 1986, 18TH P ACM S THEOR C, P220

[7]

LANDAU GM, 1987, LECTURE NOTES COMPUT, V267, P314

[8] PARALLEL EAR DECOMPOSITION SEARCH (EDS) AND ST-NUMBERING IN GRAPHS [J].

MAON, Y ;

SCHIEBER, B ;

VISHKIN, U .

THEORETICAL COMPUTER SCIENCE, 1986, 47 (03) :277-298

[9] AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM [J].

TARJAN, RE ;

VISHKIN, U .

SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :862-874

[10]

TSIN YH, 1986, IEEE T COMPUT, V35, P764, DOI 10.1109/TC.1986.1676830

← 1 2 →