PARALLEL ALGORITHMS FOR EVALUATING SEQUENCES OF SET-MANIPULATION OPERATIONS

被引：5

作者：

ATALLAH, MJ ^{[1
]}

GOODRICH, MT ^{[1
]}

KOSARAJU, SR ^{[1
]}

机构：

[1] JOHNS HOPKINS UNIV,BALTIMORE,MD 21218

来源：

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY | 1994年 / 41卷 / 06期

关键词：

DIVIDE-AND-CONQUER; OFF-LINE EVALUATION; PARALLEL COMPUTATION; PARALLEL DATA STRUCTURES;

D O I：

10.1145/195613.195617

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e., finding the response to every operation in S and returning the resulting set). We show that the problem of evaluating S is in NC for various combinations of common set-manipulation operations. Once we establish membership in NC (or, if membership in NC is obvious), we develop techniques for improving the time and/or processor complexity.

引用

页码：1049 / 1088

页数：40

共 33 条

[1] A SIMPLE PARALLEL TREE CONTRACTION ALGORITHM [J].